Способы определения истинности логического высказывания

Способы определения истинности логического высказывания

Тема 3. Основы математической логики 1. Логические выражения и логические операции.
2. Построение таблиц истинности и логических функций.
3. Законы логики и преобразование логических выражений.
Лабораторная работа № 3. Основы математической логики.

1. Логические выражения и логические операции

Исследования в алгебре логики тесно связаны с изучением высказываний (хотя высказывание — предмет изучения формальной логики). Высказывание — это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности (Аристотель).

Простым высказыванием называют повествовательное предложение, относительно которого имеет смысл говорить, истинно оно или ложно.

Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.

Примеры высказываний:

1. Москва – столица России.
2. Число 27 является простым.
3. Волга впадает в Каспийское море.

Высказывания 1 и 3 являются истинными. Высказывание 2 – ложным , потому что число 27 составное 27=3*3*3.

Следующие предложения высказываниями не являются:

• Давай пойдем гулять.
• 2*x>8.
• a*x2+b*x+c=0.
• Который час?

Итак, отличительным признаком высказывания является свойство быть истинным или ложным, последние четыре предложения этим свойством не обладают.

С помощью высказываний устанавливаются свойства, взаимосвязи между объектами. Высказывание истинно, если оно адекватно отображает эту связь, в противном случае оно ложно.

Примеры высказываний:

1. Сегодня светит солнце.
2. Трава растет.

Каждое из этих высказываний характеризует свойства или состояние конкретного объекта (в пермом предложении — погоды, во втором — окружающего мира). Каждое из этих высказываний несет значение «истина» или «ложь».

В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно — 0.

Простые высказывания назвали логическими переменными, а сложные — логическими функциями. Значения логической функции также только 0 или 1. Для простоты записи высказывания обозначаются латинскими буквами А, В, С.

Однако определение истинности высказывания далеко не простой вопрос. Например, высказывание «Число 1 +22 = 4294 967297 — простое», принадлежащее Ферма (1601-1665), долгое время считалось истинным, пока в 1732 году Эйлер (1707-1783) не доказал, что оно ложно. В целом, обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания «Сумма углов треугольника равна 180°» устанавливается геометрией, причем в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным.

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

Существуют разные варианты обозначения истинности и ложности логических переменных:

Сложные (составные) высказывания представляют собой набор простых высказываний (по крайней мере двух) связанных логическими операциями.

С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением).

Логическое выражение — это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).

Связки «НЕ», «И», «ИЛИ» заменяются логическими операциями инверсия, конъюнкция, дизъюнкция. Это основные логические операции, при помощи которых можно записать любое логическое выражение.

Введем перечисленные логические операции.

Конъюнкция — логическое умножение (от латинского conjunctio — союз, связь):

• в естественном языке соответствует союзу «И» ;
• в алгебре высказываний обозначение «&» ;
• в языках программирования обозначение «And».

Конъюнкция — это логическая операция, ставящая в соответствие каждым двум простым (или исходным) высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Если хотя бы одно из составляющих высказываний ложно, то и полученное из них с помощью союза «И» сложное высказывание также считается ложным.

В алгебре множеств конъюнкции соответствует операция пересечения множеств, т.е. множеству получившемуся в результате умножения множеств А и В соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам.

Источник

Способы определения истинности логического высказывания

Простые и сложные высказывания, логиче­ские переменные и логические константы, логическое отрицание, логическое умноже­ние, логическое сложение, таблицы истин­ности для логических операций

Для автоматизации информационных процессов необходимо уметь не только единообразно представ­лять информацию различных видов (числовую, текс­товую, графическую, звуковую) в виде последова­тельностей нулей и единиц, но и определять дейст­вия, которые можно выполнять над информацией. Выполнение таких действий производится в соответ­ствии с правилами, которым подчиняется процесс мышления. Говоря иначе, в соответствии с законами логики. Термин «логика» образован от древнегрече­ского слова 1 о§ 08 , означающего «мысль, рассуждение, закон». Наука логика изучает законы и формы мыш­ления, способы доказательств.

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

Высказывание — суждение, сформулированное в виде по­вествовательного предложения, о котором можно сказать, истинно оно или ложно.

Например, вопросительные предложения «В каком году было первое летописное упоминание о Москве?» и «Что является внешней памятью компьютера?» или побудительное предло­жение «Соблюдайте правила техники безопасности в компью­терном классе» высказываниями не являются. Повествователь­ные предложения «Первое летописное упоминание о Москве было в 1812 г.», «Оперативное запоминающее устройство являет­ся внешней памятью компьютера» и «В компьютерном классе не надо соблюдать правила техники безопасности» являются выска­зываниями, поскольку это суждения, о каждом из которых мож­но сказать, что оно ложно. Истинными высказываниями будут суждения «Первое летописное упоминание о Москве было в 1147 г.», «Жесткий магнитный диск является внешней памятью компьютера».

Каждому высказыванию соответствует только одно из двух значений: или «истина», или «ложь», которые являются логиче­скими константами. Истинное значение принято обозначать цифрой 1, а ложное значение — цифрой 0. Высказывания можно обозначать с помощью логических переменных, в качестве кото­рых используются заглавные латинские буквы. Логические пере­менные могут принимать только одно из двух возможных значе­ний: «истина» или «ложь». Например, высказывание «Информа­ция в компьютере кодируется с помощью двух знаков» можно обозначить логической переменной А, а высказывание «Прин­тер является устройством хранения информации» можно обо­значить логической переменной В. Поскольку первое выска­зывание соответствует действительности, то А = 1. Такая запись означает, что высказывание А истинно. Так как второе высказы­вание не соответствует действительности, то В = 0. Такая запись означает, что высказывание в ложно.

Высказывания могут быть простыми и сложными. Высказывание называется простым, если никакая его часть не является высказыванием. До сих пор были приведены примеры простых высказываний, которые обозначались логическими перемены ми. Выстраивая цепочку рассуждений, человек с помощью логических операций объединяет простые высказывания в сложнее’ высказывания. Чтобы узнать значение сложного высказывания нет необходимости вдумываться в его содержание. Достаточно знать значение простых высказываний, составляющих сложное высказывание, и правила выполнения логических операций.

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

Все рассуждения человека, а также работа современных тех­нических устройств основываются на типовых действиях с ин­формацией — трех логических операциях: логическом отрица­нии (инверсии), логическом умножении (конъюнкции) и логи­ческом сложении (дизъюнкции).

Логическое отрицание простого высказывания получают до­бавлением слов «Неверно, что» в начале простого высказывания.

■ ПРИМЕР 1. Имеется простое высказывание «Крокодилы уме­ют летать». Результатом логического отрицания будет высказы­вание «Неверно, что крокодилы умеют летать». Значение ис­ходного высказывания — «ложь», а значение нового — «истина».

■ ПРИМЕР 2. Имеется простое высказывание «Файл должен иметь имя». Результатом логического отрицания будет высказы­вание «Неверно, что файл должен иметь имя». Значение исход­ного высказывания — «истина», а значение нового высказыва­ния — «ложь».

Можно заметить, что логическое отрицание высказывания истинно, когда исходное высказывание ложно, и наоборот, ло­гическое отрицание высказывания ложно, когда исходное вы­сказывание истинно.

Логическое отрицание (инверсия) — логическая операция, ставящая в соответствие простому высказыванию новое высказывание, значение которого противоположно значе­нию исходного высказывания.

Обозначим простое высказывание логической переменной А. Тогда логическое отрицание этого высказывания будем обозначать НЕ А. Запишем все возможные значения логической переменной А и соответствующие результаты логического отрицания НЕ А в виде таблицы, которая называется таблицей истинности для логичес­кого отрицания (табл. 40).

ТАБЛИЦА ИСТИННОСТИ ДЛЯ ЛОГИЧЕСКОГО ОТРИЦАНИЯ

Если/1 = 0, то НЕ А = 1 (см. пример 1).

Если А = 1, то НЕ А = 0 (см. пример 2)

Можно заметить, что в таблице истинности для логическо­го отрицания ноль меняется на единицу, а единица меняется на ноль.

Логическое умножение двух простых высказываний получа­ют объединением этих высказываний с помощью союза и. Разбе­рем на примерах 3—6, что будет являться результатом логическо­го умножения.

■ ПРИМЕР 3. Имеются два простых высказывания. Одно выска­зывание — «Карлсон живет в подвале». Другое высказывание — «Карлсон лечится мороженым».

Результатом логического умножения этих простых высказы­ваний будет сложное высказывание «Карлсон живет в подвале, и Карлсон лечится мороженым». Можно сформулировать новое высказывание более кратко: «Карлсон живет в подвале и лечится мороженым». Оба исходных высказывания ложны. Значение но­вого сложного высказывания также «ложь».

■ ПРИМЕР 4. Имеются два простых высказывания. Первое вы­сказывание — «Карлсон живет в подвале». Второе высказыва­ние — «Карлсон лечится вареньем».

Результатом логического умножения этих простых выска­зываний будет сложное высказывание «Карлсон живет в подва­ле и лечится вареньем». Первое исходное высказывание ложно, а второе истинно. Значение нового сложного высказывания — «ложь».

■ ПРИМЕР 5. Имеются два простых высказывания. Первое вы­сказывание — «Карлсон живет на крыше». Второе высказыва­ние — «Карлсон лечится мороженым».

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

* ПРИМЕР б . Имеются два простых высказывания. Одно высказывание — «Карлсон живет на крыше». Другое высказывание «Карлсон лечится вареньем».

Результатом логического умножения этих простых высказываний будет сложное высказывание «Карлсон живет на крыше и лечится вареньем». Оба исходных высказывания истинны. Зпачение нового сложного высказывания также «истина».

Можно заметить, что логическое умножение двух высказываний истинно только в одном случае — когда оба исходных высказывания истинн ы.

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

ТАБЛИЦА ИСТИННОСТИ ДЛЯ ЛОГИЧЕСКОГО УМНОЖЕНИЯ

Источник

Логика высказываний: теория и применение. Примеры решений задач

Будут и задачи для самостоятельного решения, к которым можно посмотреть ответы.

Логика высказываний: определение и применение

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

Высказываниями принято считать такие предложения (написанные на «словесном» либо математическом языке), о которых можно сказать одно из двух: либо они являются истинными, либо ложными.

С математическими высказываний проще всего: они всегда имеют либо значение «истина», либо значение «ложь». Для высказываний, сделанных на «словесном» языке, понятия «истинности» и «ложности» несколько более расплывчаты. Однако, например, такие словесные формы, как «Иди домой» и «Идёт ли дождь?», не являются высказываниями. Поэтому понятно, что высказываниями являются такие словесные формы, в которых что-либо утверждается. Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования. Их невозможно оценить значениями «истина» и «ложь».

Логика высказываний отвлекается от содержательной нагрузки высказываний и изучает их истинностное значение, то есть является ли высказывание истинным или ложным.

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

Логические операции над высказываниями

Итак, высказывания можно рассмотривать как величину, которая может принимать два значения: «истина» и «ложь».

Например, даны суждения: «собака — животное», «Париж — столица Италии», «3 A ∧ B и которое истинно тогда и только тогда, когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний связкой «и».

Таблица истинности для конъюнкции:

A	B	A ∧ B
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

2. Вторая логическая операция над высказываниями A и B — дизъюнкция, выражаемая в виде A ∨ B , определяется следующим образом: оно истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно. В обычной речи эта операция соответствует соединению высказываний связкой «или». Однако здесь мы имеем не разделительное «или», которое понимается в смысле «либо-либо», когда A и B не могут быть оба истинны. В определении логики высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при истинности обоих высказываний A и B.

Таблица истинности для дизъюнкции:

A	B	A ∨ B
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

3. Третья логическая операция над высказываниями A и B, выражаемая в виде A → B ; полученное таким образом высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой, B — следствием, а высказывание A → B — следованием, называемая также импликацией. В обычной речи эта операция соответствует связке «если — то»: «если A, то B«. Но в определении логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно высказывание B. Это обстоятельство можно кратко сформулировать так: «из ложного следует всё, что угодно». В свою очередь, если A истинно, а B ложно, то всё высказывание A → B ложно. Оно будет истинным тогда и только тогда, когда и A, и B истинны. Кратко это можно сформулировать так: «из истинного не может следовать ложное».

Таблица истинности для следования (импликации):

A	B	A → B
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

4. Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается

A (можно встретить также употребление не символа

, а символа ¬, а также верхнего надчёркивания над A).

A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности для отрицания:

A Л И И Л

5. И, наконец, пятая логическая операция над высказываниями называется эквивалентностью и обозначается A ↔ B . Полученное таким образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба истинны или оба ложны.

Таблица истинности для эквивалентности:

A	B	A → B	B → A	A ↔ B
И	И	И	И	И
И	Л	Л	И	Л
Л	И	И	Л	Л
Л	Л	И	И	И

В большинстве языков программирования есть специальные символы для обозначения логических значений высказываний, записываются они почти во всех языках как true (истина) и false (ложь).

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

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

Связка	Обозначение	Название операции
не		отрицание
и		конъюнкция
или		дизъюнкция
если . то.		импликация
тогда и только тогда		эквивалентность

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

Пример 1. Вычислите логические значения следующих высказываний:

3) («Сосна» = «Дуб») ИЛИ («Вишня» = «Клён») ;

6) («Глаза даны, чтобы видеть») И («Под третьим этажом находится второй этаж») ;

7) (6/2 = 3) ИЛИ (7*5 = 20) .

1) Значение высказывания в первых скобках равно «истина», значение выражения во вторых скобках — также истина. Оба высказывания соединены логической операцией «И» (смотрим правила для этой операции выше), поэтому логическое значение всего данного высказывания — «истина».

2) Значение высказывания в скобках — «ложь». Перед этим зтим высказыванием стоит логическая операция отрицания, поэтому логическое значение всего данного высказывания — «истина».

3) Значение высказывания в первых скобках — «ложь», значение высказывания во вторых скобках — также «ложь». Высказывания соединены логической операцией «ИЛИ» и ни одно из высказываний не имеет значения «истина». Поэтому логическое значение всего данного высказывания — «ложь».

4) Значение высказывания в скобках — «ложь». Перед этим высказыванием стоит логическая операция отрицания. Поэтому логическое значение всего данного высказывания — «истина».

5) В первых скобках отрицается высказывание во внутренних скобках. Это высказывание во внутренних скобках имеет значение «ложь», следовательно, его отрицание будет иметь логическое значение «истина». Высказывание во вторых скобках имеет значение «ложь». Два этих высказывания соединены логической операцией «И», то есть получается «истина И ложь». Следовательно, логическое значение всего данного высказывания — «ложь».

6) Значение высказывания в первых скобках — «истина», значение высказывания во вторых скобках — также «истина». Два этих высказывания соединены логической операцией «И», то есть получается «истина И истина». Следовательно, логическое значение всего данного высказывания — «истина».

7) Значение высказывания в первых скобках — «истина». Значение высказывания во вторых скобках — «ложь». Два этих высказывания соединены логической операцией «ИЛИ», то есть получается «истина ИЛИ ложь». Следовательно, логическое значение всего данного высказывания — «истина».

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

1) «Пользователь не зарегистрирован»;

2) «Сегодня воскресенье и некоторые сотрудники находятся на работе»;

3) «Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными».

1) p — одиночное высказывание «Пользователь зарегистрирован», логическая операция: ;

2) p — одиночное высказывание «Сегодня воскресенье», q — «Некоторые сотрудники находятся на работе», логическая операция: ;

3) p — одиночное высказывание «Пользователь зарегистрирован», q — «Отправленные пользователем данные признаны годными», логическая операция: .

Решить примеры на логику высказываний самостоятельно, а затем посмотреть решения

Пример 3. Вычислите логические значения следующих высказываний:

1) («В минуте 70 секунд») ИЛИ («Работающие часы показывают время») ;

2) (28 > 7) И (300/5 = 60) ;

3) («Телевизор — электрический прибор») И («Стекло — дерево») ;

4) Не((300 > 100) ИЛИ («Жажду можно утолить водой»)) ;

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

1) «Если часы неправильно показывают время, то можно невовремя прийти на занятия»;

2) «В зеркале можно увидеть своё отражение и Париж — столица США»;

3) Не «дуб — дерево».

Пример 5. Определите логическое значение выражения

q = «Яблоко = Апельсин» ,

s = «Шапка покрывает голову» .

Формулы логики высказываний

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

В примерах 1 и 2 мы учились записывать с помощью логических операций сложные высказывания. Вообще-то они называются формулами логики высказываний.

Для обозначения высказываний, как и упомянутом примере, будем продолжать использовать буквы

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

Для построения формул логики высказываний кроме указанных выше букв используются знаки логических операций

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

Понятие формулы логики высказываний определим следуюшим образом:

1) элементарные формулы (атомы) являются формулами логики высказываний;

2) если A и B — формулы логики высказываний, то

3) только те выражения являются формулами логики высказываний, для которых это следует из 1) и 2).

Определение формулы логики высказываний содержит перечисление правил образования этих формул. Согласно определению, всякая формула логики высказываний либо есть атом, либо образуется из атомов в результате последовательного применения правила 2).

Пример 6. Пусть p — одиночное высказывание (атом) «Все рациональные числа являются действительными», q — «Некоторые действительные числа — рациональные числа», r — «некоторые рациональные числа являются действительными». Переведите в форму словесных высказываний следующие формулы логики высказываний:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

1) «нет действительных чисел, которые являются рациональными»;

2) «если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными»;

3) «если все рациональные числа являются действительными, то некоторые действительные числа — рациональные числа и некоторые рациональные числа являются действительными»;

4) «все действительные числа — рациональные числа и некоторые действительные числа — рациональные числа и некоторые рациональные числа являются действительными числами»;

5) «все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными»;

6) «не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными».

Пример 7. Составьте таблицу истинности для формулы логики высказываний , которую в таблице можно обозначить f .

Решение. Составление таблицы истинности начинаем с записи значений («истина» или «ложь») для одиночных высказываний (атомов) p , q и r . Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно «лжи» тогда, когда из «истины» следует «ложь».

p	q	r					f
И	И	И	И	И	И	И	И
И	И	Л	И	И	И	Л	И
И	Л	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	Л	И	И
Л	И	И	Л	И	Л	И	И
Л	И	Л	Л	И	Л	И	Л
Л	Л	И	И	И	И	И	И
Л	Л	Л	И	И	И	Л	И

Заметим, что никакой атом не имеет вида

Число скобок в формулах логики высказываний можно уменьшить, если принять, что

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций «по старшинству»:

В этом списке знак ↔ имеет самую большую область действия, а знак

— самую маленькую. Под областью действия знака операции понимаются те части формулы логики высказываний, к которым применяется (на которые действует) рассматриваемое вхождение этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые можно восстановить, учитывая «порядок старшинства». А при восстановлении скобок сначала расставляются все скобки, относящиеся ко всем вхождениям знака

(при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.

Пример 8. Восстановите скобки в формуле логики высказываний B ↔

Решение. Скобки восстанавливаются пошагово следующим образом:

Не всякая формула логики высказываний может быть записана без скобок. Например, в формулах А → (B → C) и

(A → B) дальнейшее исключение скобок невозможно.

Тавтологии и противоречия

Логические тавтологии (или просто тавтологии) — это такие формулы логики высказываний, что если буквы произвольным образом заменить высказываниями (истинными или ложными), то в результате всегда получится истинное высказывание.

Так как истинность или ложность сложных высказываний зависит лишь от значений, а не от содержания высказываний, каждому из которых соответствует определённая буква, то проверку того, является ли данное высказывание тавтологией, можно подставить следующим способом. В исследуемом выражении на место букв подставляются значения 1 и 0 (соответственно «истина» и «ложь») всеми возможными способами и с использованием логических операций вычисляются логические значения выражений. Если все эти значения равны 1, то исследуемое выражение есть тавтология, а если хотя бы одна подстановка даёт 0, то это не тавтология.

Таким образом, формула логики высказываний, которая принимает значение «истина» при любом распределении значений входящих в эту формулу атомов, называется тождественно истинной формулой или тавтологией.

Противоположный смысл имеет логическое противоречие. Если все значения высказываний равны 0, то выражение есть логическое противоречие.

Таким образом, формула логики высказываний, которая принимает значение «ложь» при любом распределении значений входящих в эту формулу атомов, называется тождественно ложной формулой или противоречием.

Кроме тавтологий и логических противоречий существуют такие формулы логики высказываний, которые не являются ни тавтологиями, ни противоречиями.

Пример 9. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

Решение. Составляем таблицу истинности:

И	И	И	И	И
И	Л	Л	Л	И
Л	И	Л	И	И
Л	Л	Л	Л	И

В значениях импликации не встречаем строку, в которой из «истины» следует «ложь». Все значения исходного высказывания равны «истине». Следовательно, данная формула логики высказываний является тавтологией.

Пример 10. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.

Решение. Составляем таблицу истинности:

И	И	И	И	И	И
И	И	Л	И	Л	Л
И	Л	И	Л	И	И
И	Л	Л	Л	Л	И
Л	И	И	Л	И	И
Л	И	Л	Л	Л	И
Л	Л	И	Л	И	И
Л	Л	Л	Л	Л	И

Среди значений данного высказывания одно — «ложь», остальные — «истина». Следовательно, данная формула логики высказываний не является ни тавтологией, ни противоречием.

Заставляем компьютер понимать «если . то. «

То, что мы называем логическими операциями, впервые появилось предположительно в Древней Греции для доказательства философских постулатов. А в наше время логические операции наиболее широко применяются в компьютерной технике. Но при всём этом компьютер «не умеет» выполнять логическую операцию импликации. Она компьютеру «не понятна». Есть, однако, способ заставить компьютер понимать условие «если . то», соответствующее, как известно, импликации. Для этого вместо составного оператора «если p, то q» нужно использовать составной оператор «не p или q«. То есть, вместо .

Как видно ниже, таблица истинности для такой замещающей логической операции идентична таблице истинности для импликации.

И	И	И
И	Л	Л
Л	И	И
Л	Л	И

Пример 11. Перепишите формулу логики высказываний без использования импликации и эквиваленции, пользуясь тождеством и законами де Моргана:

;

.

Заменяем импликацию между двумя парами скобок, отрицая самый левый знак отрицания:

.

Убираем эквиваленцию между p и q и между q и не r :

.

Используя закон де Моргана, немного упрощаем и окончательно получаем:

.

Посылки и выводы. Валидный и не валидный аргумент

Пусть есть высказывания, которые можно назвать посылками. Пусть также есть высказывание, которое можно назвать выводом. Словосочетание «можно назвать» используется при условии, что посылки связываются с выводом. То есть, из посылок логически следует вывод. Тогда, если посылки имеют значения «истина» и вывод тоже имеет значение «истина», то аргумент является валидным. Если же посылки имеют значения «истина», а вывод имеет значение «ложь», то аргумент не является валидным. Синонимы понятия «валидность» (в рассматриваемом здесь значении) — «логическая правильность», «резонность».

Пример валидного аргумента:

• Посылка. A и B — программисты
• Посылка. A и B разрабатывают программы для бухгалтеров
• Вывод. Есть программисты, которые разрабатывают программы для бухгалтеров

То есть, из посылок логически следует вывод.

Пример не валидного аргумента:

• Посылка. Запись числа может содержать запятую
• Посылка. В предложении может быть запятая
• Вывод. Есть числа, которые называются предложениями

То есть, из посылок логически не следует вывод.

Пример 12. Проверьте валидность аргумента, если

• Посылка.
• Посылка.
• Вывод.

Решение. Составляем таблицу истинности:

И	И	Л	И	И	И
И	Л	Л	Л	Л	И
Л	И	И	И	И	Л
Л	Л	И	И	И	И

В третьей строке обе посылки истинны, а вывод — ложный. Следовательно, аргумент не валидный. Таким образом, в аналогичных задачах подозрительными являются те строки, в которых все посылки истинны. Если вывод также истинный, то аргумент валидный, если ложный, то аргумент не валидный, как в этом примере. Если же посылки или обе ложны, или ложна одна из них, то такие строки не играют роли в проверке аргумента на валидность, каким бы ни было значение вывода.

Применение логики высказываний в информатике и программировании

Логика высказываний применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений «ложь» или «истина», от которых зависит ход дальнейшего исполнения программы. В небольших программах, где задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, «флаг» («flag») и подразумевается, что «флаг поднят», когда значение этой переменной — «истина» и «флаг опущен», когда значение этой переменной — «ложь». В программах большого объёма, в которых несколько или даже очень много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.

Так, может быть объявлена логическая переменная с именем «ПользовательЗарегистрирован» (или его англоязычный аналог), имеющая форму высказывания, которой может быть присвоено логическое значение «истина» при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения переменных могут меняться в зависимости от того, какое логическое значение («истина» или «ложь») имеет переменная «ПользовательЗарегистрирован». В других случах переменной, например, с именем «ДоДняХОсталосьБолееТрёхДней», может быть присвоено значение «Истина» до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на «ложь» и от значения этой переменной зависит ход дальнейшего исполнения программы.

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

Источник