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

Прописными буквами латинского алфавита А, В, …, Х, У, Z (возможно с индексами) будем обозначать пропозициональные (высказывательные) переменные. Значениями пропозициональных переменных являются элементарные высказывания.

Формулой (пропозициональной) логики высказываний называется выражение, построенное из пропозициональных переменных с помощью логических связок по следующим правилам:

1. Любая пропозициональная переменная, а также символы истины «1» и лжи «0» есть формула.

2. Если А и В – формулы, то , (А Ù В), (А Ú В), (А ® В), (А «В) – тоже формулы.

3. Других формул нет.

В дальнейшем формулу логики высказываний будем называть формулой.

Пример. Представить формулой следующее высказывание: «Если идет дождь, то надо взять зонт».

Решение. Высказывание состоит из двух простых: А – «Идет дождь»,
В – «Надо взять зонт». Тогда формула имеет вид: (А ® В).

Для сокращения записи формул условимся в формулах опускать внешние скобки. Условимся также о приоритете логических связок, в соответствии с которым отрицание «Ø» имеет высокий приоритет и выполняется прежде всего. Следующий по рангу приоритет (по убыванию) имеют конъюнкция «Ù», дизъюнкция «Ú», импликация «®», эквиваленция ««». Зная приоритет логических связок, можно опускать те пары скобок, без которых ясен порядок выполнения логических связок. Тогда, например, формулу
(А ® В)можно записать в виде А ® В, формулу (((А Ù В) Ú С) ® D) –
в виде А Ù В Ú С ® D.

Любая формула логики высказываний задает форму для получения сложных высказываний. Пусть, например, задана формула А Ù В ® С. Тогда, если пропозициональным переменным А, В, С придать значения элементарных высказываний «2 × 2 = 4», «3 + 5 = 8», «10 – 3 = 5» соответственно, то получим высказывание «если «2 × 2 = 4» и «3 + 5 = 8», то «10 – 3 = 5»». Если учесть, что первые два высказывания имеют логическое значение «истина» (1), а третье – «ложь» (0), тогда, используя логические операции, можно сделать заключение, что полученное высказывание имеет логическое значение «ложь» (0). Если вместо пропозициональных переменных А, В, С подставить другие элементарные высказывания, то получим новое высказывание, которое будет иметь свое логическое значение 0 или 1.

Замечание. Логические символы «1» и «0» являются пропозициональными константами, им соответствуют любое истинное и любое ложное высказывание соответственно.

Таким образом, мы подошли к понятию логического (истинностного) значения формулы.

Логическим значением пропозициональной переменной будем называть логическое значение элементарного высказывания, которое принимает пропозициональная переменная. Логические значения пропозициональных переменных «1», «0».

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

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

Все логические значения формулы в зависимости от логических значений входящих в нее пропозициональных переменных могут быть полностью описаны с помощью таблицы истинности. Каждому варианту логических значений пропозициональных переменных соответствует отдельная строка таблицы истинности. Если в формуле имеется n различных пропози-циональных переменных, то для них возможны 2 ⁿ различных вариантов логических значений. Таблица истинности для такой формулы содержит 2 ⁿ строк. Для облегчения построения таблицы истинности в нее включают столбцы, соответствующие промежуточным вычислениям.

Пример. Определить всевозможные логические значения формулы Z =
= А Ù Ú .

Решение. Задача может быть решена путем перебора всевозможных логических значений переменных А и В с помощью таблицы истинности.

Расширенная таблица истинности для нашей формулы Z содержит
2² = 4 строк и имеет вид:

А	В		А Ù		Z

Множество всех формул логики высказываний разбивается на три непересекающихся подмножества (класса):

1) тождественно ложные формулы (противоречия), принимающие только логическое значение «0» при любых логических значениях входящих в них пропозициональных переменных;

2) тождественно истинные формулы (тавтологии), принимающие только логическое значение «1» при любых логических значениях входящих в них пропозициональных переменных;

3) формулы, принимающие оба логические значения «0» и «1» на разных наборах логических значений пропозициональных переменных.

Очевидно, что если F – формула противоречия (тавтология), то ее отрицание – тавтология (противоречие). Например, формула Х Ù У ® Х является тождественно истинной (тавтология).

3. Основные эквивалентные преобразования формул
(законы логики высказываний)

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

Таблицы истинности для эквивалентных формул совпадают (с точностью до перестановки строк).

Можно показать, что две формулы F и G эквивалентны тогда и только тогда, когда формула F «G – тавтология.

В логике высказываний иногда приходится проводить преобразования формул, сохраняющие эквивалентность. Для таких преобразований используют законы логики высказываний, которые имеют вид эквивалентностей (равносильностей).

Пусть А, В, С – некоторые формулы логики высказываний, тогда следующие формулы эквивалентны:

  – идемпотентность.

1. А Ù А = А

2. А Ú А = А

3. – закон двойного отрицания.

  – свойства констант.

4. А Ù 1 = А, А Ú 1 = 1

5. А Ù 0 = 0, А Ú 0 = А

6. А Ù = 0 – закон противоречия.

7. А Ú = 1 – закон исключенного третьего.

  – закон поглощения.

8. А Ú (А Ù В) = А

9. А Ù (А Ú В) = А

  – коммутативность.

10. А Ú В = В Ú А

11. А Ù В = В Ù А

  – ассоциативность.

12. А Ù (В Ù С) = (А Ù В) Ù С

13. А Ú (В Ú С) = (А Ú В) Ú С

  – дистрибутивность.

14. А Ù (В Ú С) = (А Ù В) Ú (А Ù С)

15. А Ú (В Ù С) = (А Ú В) Ù (А Ú С)

  – законы Де Моргана.

16.

17.

18. А ® В = ® – закон контрапозиции.

19. А «В = « – закон противоположности.

20. А ® В = Ú В.

21. А «В = (А ® В) Ù (В ® А).

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

Пример. Трое мужчин – Вася, Гриша, Миша – пришли в цирк со своими детьми: Сашей, Петей и Колей. К детям подошел клоун и спросил: «Кто твой папа?» Каждый из детей сказал следующее:

Саша: Я сын Васи, Петя – сын Гриши.

Петя: Я сын Васи, Коля – сын Гриши.

Коля: Я сын Васи, Петя – сын Миши.

В ответах каждого из них одно утверждение истинно, а другое – нет. Требуется определить, кто чей папа.

Решение. Обозначим через ХY ребенка, имя которого начинается с буквы Х, а Y – имя папы. Тогда их высказывания можно записать так: СВ и ПГ, ПВ и КГ, КВ и ПМ.

Так как по условию задачи одно из парных высказываний верно,
а другое – нет, то можно составить следующие истинные дизъюнкции:

СВ Ú ПГ = 1, ПВ Ú КГ = 1, КВ Ú ПМ = 1.

Но тогда будет истинной и конъюнкция этих дизъюнкций:

(СВ Ú ПГ) Ù (ПВ Ú КГ) Ù (КВ Ú ПМ) = 1.

Используя основные эквивалетные преобразования к первой и второй скобке, имеем:

(СВ Ú ПГ) Ù (ПВ Ú КГ) =
= (СВ Ù ПВ) Ú (СВ Ù КГ) Ú (ПГ Ù ПВ) Ú (ПГ Ù КГ) =
= 0 Ú (СВ Ù КГ) Ú 0 Ú 0 = СВ Ù КГ.

XY Ù XY = 0, так как у каждого мужчины по одному ребенку.

XY Ù XZ = 0,так как один ребенок не может быть сыном двух пап.

Тогда конъюнкция примет вид:

(СВ Ù КГ) Ù (КВ Ú ПМ) = 1.

Аналогично, используя основные эквивалентные преобразования, имеем:

(СВ Ù КГ) Ù (КВ Ú ПМ) = СВ Ù КГ Ù КВ Ú СВ Ù КГ Ù ПМ =
= 0 Ú СВ Ù КГ Ù ПМ.

Таким образом: Саша сын Васи, Коля сын Гриши, Петя сын Миши.

Если формула F содержит подформулу F ₁, эквивалентную формуле F ₂, то возможна подстановка всюду в формуле F вместо F ₁ формулы F ₂ без изменения истинности формулы F. В результате такой подстановки будет получаться эквивалентная формула. Это дает возможность упрощать формулы, используя основные эквивалентные преобразования.

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

Пример. Упростить формулу .

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

= (п. 16) = = (пп. 17, 16) =

= = (пп. 13, 3) = = (п. 8) = Z =

= (п. 20) = Х ® Z.

Дата добавления: 2015-10-21