7. Алгебра высказываний. Пропозициональные формулы.

Отрицание

Если А есть высказывание, то k (‖не-А‖) является отрицанием А. Для каждой логической операции можно построить так называемую истинностную таблицу (ИТ), в которой обозначены результаты операций при всех возможных значениях операндов. Для отрицания ИТ примет следующий вид:

Аך A

И Л

ЛИ

Коньюнкция

Также называется логическим умножением. Таблица истинности:

А В А & B

И И И

Л И Л

И Л Л

Л Л Л

Дизьюнкция

Также называется логическим сложением. Таблица истинности:

А В А V B

И И И

Л И И

И Л И

Л Л Л

Импликация

Импликация означает следование - ”если А, то В”. Это высказывание ложно только в том случае, когда А - истинно, а В - ложно. Разумеется, бывают случаи, когда смысл А и В неясен, а поэтому говорить об истинности результата очень трудно. Например:

Если на Марсе ходят поезда, то марсианские поезда синего цвета Таблица истинности для импликации:

А В А → B

И И И

Л И И

И Л Л

Л Л И

Эквивалентность

Последняя операция называется эквивалентностью. Таблица истинности для нее выглядит так:

АВ А ≡B

И И И

Л И Л

И Л Л

Л Л И

Запись А ≡ B читается так: ”А тогда и только тогда, когда В”. Когда мы говорим ‖А тогда и только тогда, когда В‖, то имеем в виду, что оба предложения А и В одновременно истинны, либо одновременно ложны.

Пропозициональные формулы

Символы ך,&,V,→,≡ называются пропозициональными связками. Латинскими заглавными буквами будем обозначать пропозициональные буквы, или высказывания. Тогда:

1.Все пропозициональные буквы есть пропозициональные формулы (ПФ).

2.Если А и В - пропозициональные формулы, то (ך), (A & B), (A V B), (А → B), (А ≡ B) – тоже пропозициональные формулы.

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

Всякая ПФ определяет некоторую истинностную функцию, которую можно представить истинностной таблицей, которая устанавливает соответствие между всеми возможными наборами переменных, входящих в формулу и значениями формулы. Таблицы истинности применяются для:

• вычисления истинности сложных высказываний;

•установления эквивалентности высказываний;

•определения тавтологий. Рассмотрим ПФ и построим для нее ИТ.

((A ≡ B ) → (( ך A) & B))

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

8. Интерпретация, тавтология, противоречие. Логическое следование и логическая эквивалентность.

Определение. Каждому атому, входящему в формулу, можно приписать значение истина или ложь. Каждая возможная комбинация таких значений, приписанных атомам формулы, называется интерпретацией. Формула может быть истинной при одной интерпретации и ложной при другой. Значение формулы А в интерпретации I будем обозначать I(A). Формула, истинная при некоторой интерпретации, называется выполнимой. Формула, истинная при всех возможных интерпретациях, называется общезначимой (тавтологией). Формула, ложная при всех возможных интерпретациях, называется невыполнимой, или противоречием.

Пример тавтологии: (AV(ךA))

Доказательство легко проводится построением ИТ.

Доказать тавтологию: (A & B) → (A V B)

Для доказательства строим ИТ:

( A & B ) → ( A V B )

И И И И И И И

И Л Л И И И Л

Л Л И И Л И И

Л Л Л И Л Л Л

Пример противоречий: (A ≡ ( ךA )), (A & ( ךA ))

Следование и эквивалентность

Формулы А и В являются логически эквивалентными, если при любых значениях переменных, входящих в эти формулы значение А совпадает со значением В. Если A и В - эквивалентны, то (A ≡ B) - тавтология. Логически эквивалентные формулы будем обозначать знаком ‖=‖. Если (A → B) является тавтологией, то говорят, что A логически влечет B, или В является логическим следствием А. Логические следование и эквивалентность играют исключительно важную роль в математической логике, позволяя проводить преобразования пропозициональных формул и решать логические задачи.

Теорема Имеет место следующая логическая эквивалентность: (A→ B) = (ךAVB)

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

( A → B ) = (( ך A) V B)

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

Утверждение ―Если P, то Q, иначе R‖ широко используется в программировании может быть представлено формулой (P → Q)&(ךP →R). Ей соответствует фраза: ―Если Р, то Q, а если не P, то R‖.

Логическая формула, представляющая приведенное выше высказывание имеет вид:A → (ךB) Существует множество формул, эквивалентных данной. Интерпретируя эти формулы в естественном языке, получим следующие утверждения, которые все эквивалентны между собой:

A → ךB Порядочный человек не может быть вором

ךAV ךB Или он не порядочный человек, или он не вор

ך(A&B) Порядочность и воровство несовместимы

B → ךA Если человек вор, то он не является порядочным человеком

Примеры логически эквивалентных формул

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

1.Отрицание дизъюнкции эквивалентно конъюнкции отрицаний (1-й закон де Моргана): ך(AVB) = (ךA)&(ךB)

2.Отрицание конъюнкции эквивалентно дизъюнкции отрицаний (2-й закон де Моргана): ך(A&B) = (ךA)V(ךB)

3.Импликация эквивалентна импликации отрицаний (контрпозиции): (A → B) = (ךA)

→ (ךB)

4.Конъюнкция и импликация: (A&B) = ך(A → (ךB))

5.Конъюнкция и дизъюнкция: (A&B) = ך(ךA V ךB)

Примеры использования законов де Моргана

Пример 1. Утверждение ―Симпсон будет признан судом виновным тогда и только тогда, когда все 12 присяжных заседателей признают его виновным‖ может быть

записано в виде формулы B≡(A1&A2&...&A12), где B означает виновность, а An - факт признания вины n-ым присяжным заседателем. Равносильная ей формула ךB≡ ך(A1&A2...&A12) по закону де Моргана может быть преобразована в формулу ךB≡ (ךA1 V ךA2 &...ךA12), которую можно интерпретировать так: ―Симпсон не будет признан судом виновным тогда и только тогда, когда хотя бы один из 12 присяжных заседателем не признает его вины‖.

Пример 2. Рассмотрим следующую задачу. Имеется текстовый файл, который необходимо прочитать посимвольно до появления любого из трех символов: (%,#,EOF). Привести возможные варианты решения этой задачи. В первую очередь нас интересует построение условия для циклической конструкции, выполняющей чтение символов из файла. Обозначим факт появления первого символа как А, второго - как В и третьего - как С. Тогда условие, при котором читаются символы из файла будет записано в виде следующей формулы: (ךA)&(ךB)&(ךC) Однако для данной формулы имеется логически эквивалентная ей конструкция: ך(A V B V C) Поэтому можно предложить два варианта реализации цикла чтения содержимого файла на языке программирования С.