 |
Лекция 3. Исчисление высказываний
|
|
|
|
1. Понятие высказывания
2. Операции ИВ
3. Интерпретации. Таблицы истинности
4. Равносильные формулы. Тавтологии и противоречия.
Обычно в лингвистике выделяют повествовательные, повелительные и вопросительные предложения. Рассмотрим предложения, в которых формулируется некоторая информация о предметах, явлениях, событиях, положениях дел и т. д. Такие предложения будем называть высказываниями. Высказывание - это предложение, в котором содержится какая-то информация и которое может быть оценено как истинное или ложное. Такие высказывания называют атомарными, или атомами.
Под сложными высказываниями будем понимать такие высказывания, которые образуются из других высказываний с помощью союзов “и”, “или”, “если..., то... ” и др.
Исчисление высказываний служит для представления высказываний на формальном языке. При этом отдельные высказывания обозначаются заглавными буквами латинского алфавита, союзы заменяются логическими связками. При этом действуем по правилам:
Сложное утверждение «A и B» представляем как A & B,
«А или В» - A Ú B,
«Если А, то В» (вариант «А только если В») A→ B,
« А в том, и только том случае, когда В» A~B,
«Неверно А» («Не А») А.
Такая формализация необходима для того, чтобы установить является ли высказывание истинным или ложным, используя формальные методы, которые могут быть реализованы в компьютере.
Пример 2. Представить в исчислении высказываний следующее утверждение: “Если верно, что когда идет дождь, то дорога мокрая, то справедливо также и следующее утверждение: если дорога сухая, то дождя нет”.
|
|
|
Введем следующие обозначения:
А - идет дождь;
В - дорога мокрая.
Тогда утверждение представляется следующей логической формулой:
(А®В)®(Ø В®Ø А).
Дадим определение логических связок
Пусть A и B - высказывания, принимающие два значения: истина (И) или ложь (Л). Символы И и Л называются истинностными значениями.
Определим A & B как высказывание, истинное только при одновременной истинности A и B.
| A | B | A & B |
| Л | Л | Л |
| Л | И | Л |
| И | Л | Л |
| И | И | И |
Аналогично определим высказывания А (значение высказывания меняется на противоположное), A Ú B (истинно, если истинно хотя бы одно из утверждений), A→ B (ложно только в случае, когда из истинного А получено ложное B), A~B (истинно, только когда A и B имеют одинаковые значения: оба истинны, или оба ложны)
| A | B | А | B | A Ú B | A→ B | A~B |
| Л | Л | И | И | Л | И | И |
| Л | И | И | Л | И | И | Л |
| И | Л | Л | И | И | Л | Л |
| И | И | Л | Л | И | И | И |
Если в сложном высказывании известно, какие значения принимают все входящие в него атомарные высказывания, всегда можно определить истинность или ложность всего утверждения.
Так, для сложного высказывания (А®В)®(Ø В®Ø А) в случае, когда A = И, а B = Л, мы можем выполнить подстановку истинностных значений в формулу и получить (И®Л)®(Ø Л®Ø И) = (И®Л)® (И®Л) = (Л®Л) = И
Понятие интерпретации.
Если в сложном высказывании известны все истинностные значения атомарных высказываний, скажем, что мы задали интерпретацию данного высказывания. Если логическая формула после приписывания конкретных истинностных значений атомам приняла значение Истина, скажем, что формула истинна в данной интерпретации. В противном случае скажем, что формула ложна в данной интерпретации. Для формулы (А®В)®(Ø В®Ø А) существуют всего четыре интерпретации, представленные в таблице.
|
|
|
| A | B | (А®В)®(Ø В®Ø А) |
| Л | Л | |
| Л | И | |
| И | Л | И |
| И | И |
Самостоятельно найдите значения формулы для остальных интерпретаций.
Для произвольной логической формулы, содержащей n атомарных высказываний, существует точно 2n различных интерпретаций. Таблица, содержащая все возможные интерпретации логической формулы, называется таблицей истинности.
Пример 3. Рассмотрим утверждение «Будет ветреная погода или будет туман и пойдет дождь».
Обозначим атомарные высказывания: V - Будет ветреная погода,
T - будет туман,
D - пойдет дождь.
Сложное высказывание представим формулой VÚ T& D. Для этой формулы существует 23 = 8 различных интерпретаций, соответственно, таблица истинности будет содержать 8 строк:
| V | T | D | T& D | VÚ T& D |
| Л | Л | Л | Л | Л |
| Л | Л | И | Л | Л |
| Л | И | Л | Л | Л |
| Л | И | И | И | И |
| И | Л | Л | Л | И |
| И | Л | И | Л | И |
| И | И | Л | Л | И |
| И | И | И | И | И |
О приоритетах логических операций.
Решая предыдущую задачу, мы построили таблицу истинности по сути для формулы VÚ (T& D). Для сокращения количества скобок в логических формулах также, как и в алгебре, принято учитывать приоритеты логических операций (связок). Так, наивысший приоритет имеет операция «отрицание» Ø . Следующей по старшинству является операция & (конъюнкция, или логическое умножение), после нее выполняется операция Ú (дизъюнкция, или логическое сложение), и, наконец, операции ® (импликация) и ~ (эквивалентность) имеют низший приоритет и выполняются в последнюю очередь.
Так, в формуле X®Y& Z Ú Ø X& Z & Y
первоначально вычисляем Ø X, затем находим два логических произведения Y& Z и Ø X& Z & Y. Следующим шагом выполняем операцию «или»: Y& Z Ú Ø X& Z & Y. В последнюю очередь находим импликацию ®.
Приоритет логических операций можно изменить, используя скобки.
В формуле (X®Y)& (Z Ú Ø X)& Z& Y порядок вычислений меняется. Первоначально выполняем операции в скобках (X®Y) и (Z Ú Ø X). Затем последовательно перемножаем четыре логические сомножителя. Определите самостоятельно последовательность операций в формулах
|
|
|
(X®Y& Z) Ú Ø X& Z & Y и X®(Y& Z) Ú Ø (X& Z & Y).
Таблица истинности, построенная нами для формулы VÚ T& D, содержит восемь интерпретаций. На некоторых интерпретациях логическ5ая формула истинна, а на некоторых – ложна.
Определение 1 Две логические формулы, значения которых совпадают на всех интерпретациях, называются равносильными.
Так, равносильны формулы A& (B& C) и (A& B)& C. Для таких формул ставим знак =. Убедиться в том, что две формулы равносильны, можно построением таблиц истинности, или последовательным преобразованием этих формул.
Пример 4. Убедимся в том, что две формулы Ø AÚ Ø B и Ø (A& B) равносильны. Построим две таблицы
| A | B | А | B | Ø A Ú Ø B |
| Л | Л | И | И | И |
| Л | И | И | Л | И |
| И | Л | Л | И | И |
| И | И | Л | Л | Л |
| A | B | A & B | Ø (A & B) |
| Л | Л | Л | И |
| Л | И | Л | И |
| И | Л | Л | И |
| И | И | И | Л |
Мы видим, что на всех интерпретациях значения формул совпали. Таким образом, Ø AÚ Ø B = Ø (A& B)
Введём важные классы формул.
Определение 2 Формула, принимающая значение Истина во всех своих интерпретациях, называется тавтологией или общезначимой формулой.
Примерами тавтологий могут быть формулы
XÚ Ø X, A®AÚ B и другие. Для проверки свойства постройте их таблицы истинности.
Определение 3 Формула, принимающая значение Ложь во всех своих интерпретациях, называется противоречием, или тождественно ложной формулой.
Противоречивыми, например, являются формулы X& Ø X, Ø (A& B®A).
В исчислении высказываний, как будет показано ниже, очень важным является класс формул, тождественно истинных. Только такие формулы могут быть доказаны как теоремы в исчислении высказываний.
Как убедиться в том, что некая формула является тавтологией? Первый путь нам известен – это построение таблицы истинности. Однако, если число атомов в формуле велико, построение таблицы занимает много времени. Так как мы проверяем 2n разных интерпретаций. Существует другой путь, который заключается в приведении исходной формулы к некоторому типовому виду – стандартной форме.
|
|
|
|
|
|
