Дискретная математика - приложения логики высказываний

Высказывание — это утверждение , высказывание или повествовательное предложение, которое может быть либо истинным, либо ложным, но не тем и другим одновременно. Например, предложение «Рам пошел в школу». может быть либо истинным, либо ложным, но оба случая невозможны. Таким образом, мы можем сказать, что предложение «Рам пошел в школу». является предложением. Но предложение «N больше 100» не является предложением, поскольку мы не можем утверждать, истинно оно или ложно, если не задано значение N. Еще несколько примеров предложений: «12 — 10 = 3», «Библиотека открыта» и т. д.

Область математической логики, которая имеет дело с предложениями, называется логикой высказываний или исчислением высказываний. Он также известен как сентенциальная логика или сентенциальное исчисление . Он изучает логические значения предложений, взятых в целом, и логические отношения, когда они связаны с помощью логических связок (таких как логическое И, логическое ИЛИ и т. Д.).

Важность пропозициональной логики

Логика высказываний играет важную роль в информатике, а также в повседневной жизни человека. Основные преимущества изучения и использования логики высказываний заключаются в том, что она не позволяет нам делать противоречивые выводы и принимать неосторожные решения. Он включает в себя рассуждения и мыслительные способности в повседневной жизни.

Приложения пропозициональной логики

В области компьютерных наук логика высказываний имеет широкий спектр приложений и, следовательно, очень важна. Он используется в системных спецификациях, проектировании схем, логических головоломках и т. д. Помимо этого, его также можно использовать для перевода английских предложений в математические утверждения и наоборот. Давайте подробно рассмотрим это огромное разнообразие приложений.

1) Перевод английских предложений в логические утверждения

Как и любой другой человеческий язык, английские предложения могут быть неоднозначными. Эта двусмысленность может привести к неосведомленному принятию решений и другим фатальным ошибкам. Чтобы устранить эту двусмысленность, мы можем перевести эти английские предложения в логические выражения с помощью логики высказываний. Обратите внимание, что иногда это может включать в себя несколько предположений, основанных на предполагаемом значении предложения.

Пример: дано предложение « Вы можете купить эту книгу, если у вас есть 20 или 10 долларов и купон на скидку. «Теперь, это немного сложно понять сразу. Итак, мы переведем это в логическое выражение, которое сделает его простым для понимания. Пусть a , b , c и d представляют предложения « Вы можете купить эту книгу. “, “ У вас есть 20 долларов. “, “ У вас есть 10 долларов. ", и " У вас есть купон на скидку. " соответственно. Тогда данное предложение можно перевести как (b ∨ (c ∧ d) -> a , что просто означает, что «если у вас есть 20 или 10 долларов вместе со скидочным купоном, вы можете купить книгу».

2) Технические характеристики системы

При разработке/производстве системы (программного или аппаратного обеспечения) разработчики/производители должны соответствовать определенным требованиям и спецификациям, которые обычно указываются на английском языке. Но поскольку английские предложения могут быть двусмысленными, разработчики/инженеры строго и недвусмысленно переводят эти системные спецификации в логические выражения, соответствующие государственным спецификациям.

Пример: Пусть a, b, c и d представляют предложения « Компьютер находится в локальной сети. “, “ Компьютер имеет действительный идентификатор для входа в систему. “, “ Компьютер находится под управлением администратора. “, и “ Интернет доступен для компьютера”. Таким образом, сложное предложение « Если компьютер находится в локальной сети или не находится в локальной сети, но имеет действительный идентификатор входа в систему или используется администратором, тогда Интернет доступен для компьютера. ” можно выразить как ( a ∨ (¬a ∧ b) ∨ c) -> d.

3) Логические головоломки

Головоломки, которые решаются с помощью рассуждений и логики, называются логическими головоломками. Их можно использовать для упражнений для мозга, в развлекательных целях и для проверки мыслительных способностей человека. Решить такие головоломки, как правило, сложно, но это можно легко сделать с помощью логики высказываний. Некоторые из известных логических головоломок — головоломка « грязные дети», головоломки Смалльяна о рыцарях и лжецах и т. д.

Пример:

Постановка задачи: На острове есть два типа жителей: рыцари, которые всегда говорят правду, и их противоположности, лжецы, которые всегда лгут. Вы встречаете двух людей A и B. Определите, кто такие A и B, если A говорит, что B — лжец, а B говорит: «Мы оба одного типа»?

Решение . Пусть p и q — утверждения о том, что A — рыцарь и B — рыцарь соответственно, поэтому ¬p и ¬q — утверждения о том, что A — лжец и B — лжец соответственно. Предположим, что A — рыцарь, т. е. p истинно. Итак, A говорит правду, а это значит, что ¬q верно. Теперь, поскольку B является лжецом, все, что он говорит, является ложью, то есть (p ∧ q) ∨ (¬p ∧ ¬q) ложно, что просто означает, что если один из них лжец, то другой является рыцарем или наоборот. Теперь, согласно предположению, это утверждение верно. Таким образом, мы можем сделать вывод, что А — рыцарь, а В — лжец.

4) Булев поиск

Еще одним важным применением логики высказываний является логический поиск. Эти поиски используют методы из пропозициональной логики. Логические связки широко используются при поиске в больших массивах информации, таких как указатели веб-страниц. В логическом поиске связка И используется для поиска записей, содержащих оба термина, связка ИЛИ используется для поиска записей, содержащих один или оба термина, а связка НЕ, также записываемая как И НЕ, используется, когда нам нужно исключить определенный поисковый запрос.

Пример. Некоторые поисковые системы поддерживают поиск по веб-страницам с использованием булевых методов. Например, если мы хотим найти веб-страницы о походах в Западные Альпы, мы можем искать страницы, соответствующие запросу ЗАПАД И АЛЬПЫ И ПОХОДЫ. И если нам нужны веб-страницы о походах в Альпы, но не в Западные Альпы, то мы можем искать страницы, соответствующие записи HIKING AND ALPS AND NOT (WEST AND ALPS).

5) Логические/компьютерные схемы

Логические вентили или схемы — это электронные устройства, реализующие булевы функции, т. е. они выполняют логическую операцию над одним или несколькими входными битами и выдают бит на выходе. Они являются основными строительными блоками любой цифровой системы. Отношения между входом и выходом основаны на определенной пропозициональной логике.

Пример: логические вентили называются вентилями И, вентилями ИЛИ, вентилями НЕ и т. д. на основе имен логических связок И, ИЛИ, НЕ и т. д. Выходные значения истинности для заданных входных битов для этих вентилей такие же, как и возвращаемые логическими связками.

6) Вывод и принятие решений

Логика высказываний широко используется в правилах вывода и принятия решений. Затем эти правила вывода можно использовать для построения аргументов. Когда дано несколько предпосылок, трудно сказать, верен ли данный аргумент. Таким образом, мы используем эти правила вывода для подтверждения аргумента и принятия решения.

Пример: мы можем доказать, что следующие посылки составляют правильный аргумент, используя правило вывода.

« Если сегодня вторник, у меня контрольная по английскому языку или естественным наукам. Если мой профессор английского отсутствует, то у меня не будет теста по английскому языку. Сегодня вторник, и мой профессор английского отсутствует. Поэтому у меня есть тест по науке. “

T: Today is Tuesday

E: I have a test in English

S: I have a test in Science

A: My English Professor is absent

Посылки как логические обозначения

Правила вывода

Следовательно, приведенный аргумент действителен.

7) Искусственный интеллект — нечеткая логика

Алгоритмы ИИ используют нечеткую логику. В нечеткой логике нет логики абсолютной истины и абсолютной ложности. Но в нечеткой логике также присутствует промежуточное значение, которое частично истинно, а частично ложно.

Например: истинностное значение 0,6 можно присвоить утверждению «Фред счастлив», потому что Фред счастлив немного больше, чем большую часть времени, а истинностное значение 0,5 можно присвоить утверждению «Перси счастлив», потому что Перси счастлив. счастливая половина времени.