Исчисление высказываний

Высказывание есть утвердительное предложение, которое либо истинно, либо ложно, но не то и другое вместе. Примеры высказываний: «Снег белый», «Прохоров – декан». «Истина» или «ложь», приписанная некоторому высказыванию, называется истинностным значением этого высказывания. Рассмотрим три истинных предложения:

· За день до своей смерти он был еще жив;

· Если верно, что когда идет дождь, то дорога мокрая, то справедливо также и следующее утверждение: если дорога сухая, то дождя нет;

· Земля вертится.

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

Исчисление высказываний – формальная логическая система. Множество ее базовых элементов составляют логический словарь (алфавит) T из бесконечного счетного множества высказываний, обозначаемых строчными латинскими буквами (иногда с индексами) и называемых атомами и пяти элементарных логических функций (связок):

«отрицание» -Ш, ~, -, not, не;

«конъюнкция» - Щ, &, and, и;

«дизъюнкция» - Ъ, ч, or, или;

«импликация» - ®, Й, Ю;

«эквивалентность» - «, є, Ы.

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

Совокупность правил построения формул выглядит так:

· Всякий атом (высказывание) является формулой;

· Если X и Y - формулы, то Ш X, (X Щ Y), (X Ъ Y), (X ® Y) и (X «Y) – формулы;

· Никаких формул, кроме порожденных применением указанных выше правил, нет.

Круглые скобки позволяют указать порядок, в котором применялись правила. Если в примере 2 утверждений, приведенных выше, обозначим высказывание «идет дождь» буквой P, а высказывание «дорога мокрая» буквой Q, то используя правила построения все утверждение записывается следующим образом:

(P ® Q) ®(ШQ ® ШP).

P	Q	Ш P	P Щ Q	P Ъ Q	P ® Q	P «Q
И	И	Л	И	И	И	И
И	Л	Л	Л	И	Л	Л
Л	И	И	Л	И	И	Л
Л	Л	И	Л	Л	И	И

Объектами изучения естественных и формальных языков являются, в частности, синтаксис, который позволяет распознавать фразы среди наборов слов, и семантика, которая придает определенное значение фразам. Это относится и к исчислению высказываний. Любое высказывание может быть либо истинно, либо ложно. Введем семантическую область {И, Л}. Интерпретировать формулу это значит приписать ей одно из двух значений истинности: И или Л. Значение истинности формулы зависит только от стуктуры этой формулы и от значений истинности составляющих ее высказываний. Таблица истинности логических связок исчисления высказываний приведена ниже.

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

P	Q	R	ШR	P Щ Q	(P Щ Q) ® (ШR)
И	И	И	Л	И	Л
И	И	Л	И	И	И
И	Л	И	Л	Л	И
И	Л	Л	И	Л	И
Л	И	И	Л	Л	И
Л	И	Л	И	Л	И
Л	Л	И	Л	Л	И
Л	Л	Л	И	Л	И

Рассмотрим формулу: (P Щ Q) ® (ШR). Таблица истинности для нее будет выглядеть следующим образом:

Определение 1: интерпретацией формулы исчисления высказываний называется такое приписывание истинностных значений атомам формулы, при котором каждому из атомов приписано либо И, либо Л.

Определение 2: Формула истинна при некоторой интерпретации тогда и только тогда, когда она получает значение И в этой интерпретации, в противном случае формула ложна.

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

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

Если Q - тавтология, то ее обозначают как ъ= Q. Если E – множество формул, то запись E ъ= Q означает, что при всех интерпретациях, при которых истинны все формулы из E, истинна также формула Q. Формула Q называется логическим следствием из E. Таким образом, тавтология – логическое следствие из пустого множества. Если E содержит единственный элемент P, то P ъ= Q. Тогда Q является логическим следствием P тогда и только тогда, когда импликация P ® Q есть тавтология, или P ъ= Q «ъ= (P® Q). В более общем виде можно написать: { F₁, F₂,…, F_n } ъ= Q «ъ= (F₁ Щ F₂ Щ …F_n) ъ= Q.

Определение 5: Пусть даны формулы F₁, F₂,…, F_n и формула Q. Говорят, что Q есть логическое следствие формул F₁, F₂,…, F_n тогда и только тогда, когда для всякой интерпретации I, в которой F₁ Щ F₂ Щ …F_n истинна, Q также истинна. F₁, F₂,…, F_n называются аксиомами (или постулатами, или посылками, или гипотезами).

Если формулы P и Q – логические следствия друг друга, то они называются логически эквивалентными. Такая ситуация имеет место тогда и только тогда, когда формула (P «Q) является тавтологией. Понятие тавтологии совпадает с понятием теоремы в аксиоматической системе. Аксиоматическая система обладает свойством адекватности, то есть она состоит из множества аксиом, считающихся общезначимыми. Кроме аксиом в аксиоматическую систему входит множество правил вывода, позволяющих строить новые общезначимые выражения из аксиом и уже полученных общезначимых выражений. Выводимая формула обозначается ъѕ P.

Древнейшая из аксиоматических теорий – это Евклидова геометрия.

Исчисление высказываний тоже является аксиоматической системой. Любая аксиоматическая система должна удовлетворять следующим требованиям:

1. Непротиворечивость: невозможность вывода отрицания уже доказанного выражения (которое считается общезначимым);

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

3. Полнота (взаимность адекватности): любая тавтология выводима из системы аксиом. В адекватной системе аксиом любая выводимая формула есть тавтология, то есть верно, что ъѕ P® ъ= P. Соответственно в полной систем верно: ъ= P® ъѕ P.

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

Классическая система аксиом:

1. P ®(Q ® P);

2. (P ®(Q ® R))®((P ® Q)®(P ® R));

3. (ШP ® Ш Q) ® ((ШP ® Q) ® P).

Система аксиом Новикова:

1. P ®(Q ® P);

2. (P ®(Q ®R))®((P ® Q)®(P ® R));

3. P Щ Q ® P;

4. P Щ Q ® Q;

5. (P ® Q) ®((P ® R) ®(P ® Q Щ R));

6. P ® P Ъ Q;

7. Q ® P Ъ Q;

8. (P ® R) ®((Q ® R) ®(P Ъ Q ® R));

9. (P ® Q) ®(Ш Q ®Ш P);

10. P ®ШШ P;

11. ШШ P ® P.

Существует три обязательных правила вывода, входящих в B в исчислении высказываний:

1. Все аксиомы выводимы.

2. Правило одновременной подстановки: если некоторая тавтология U содержит атом P, то одновременная замена всех вхождений атома P в U на любую формулу Q приводит к порождению тавтологии.

3. Modus Ponens (заключение): если P – тавтология, и P® Q, то Q – тавтология.

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

1. Если P - тавтология, то Q ® P – тавтология (доказательство следует из аксиомы 1.1 и правила вывода 3).

2. Свойство транзитивности отношения следования: если P® Q, Q® R – тавтологии, то P® R – тавтология.

3. Обобщением правила 4 является теорема дедукции: необходимым и достаточным условием выводимости Q из гипотез R, P является выводимость P® Q из R. Данную теорему можно записать следующим образом: R, P ъѕ Q «R ъѕ (P® Q).

Определение 6. Выводом формулы P из формул U₁, U₂,…, U_n называется последовательность формул F₁, F₂,…, F_n такая, что F_m есть P, а любая F_i либо аксиома, либо одна из формул U_i, либо формула, непосредственно выводимая из предшествующих ей формул.

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

1. P «Q = P ® Q Щ Q ® P;

2. P ® Q = Ш P Ъ Q;

3. Коммуникативные законы: P Ъ Q = Q Ъ P; P Щ Q = Q Щ P;

4. Ассоциативные законы:: (P Ъ Q) Ъ R = Q Ъ (P Ъ R); (P Щ Q) Щ R = Q Щ (P Щ R);

5. Дистрибутивные законы: P Ъ (Q Щ R) = (P Ъ Q) Щ (P Ъ R);
P Щ (Q Ъ R) = (P Щ Q) Ъ (P Щ R);

6. Законы идемпотентности: P Ъ P = P; P Щ P = P;

7. P Ъ Л = P; P Щ И = P;

8. P Ъ И = И; P Щ Л = Л;

9. P Ъ ШP = И; P Щ ШP = Л;

10. Ш(ШP)= P;

11. Законы де Моргана: Ш(P Ъ Q) = ШQ Щ ШP; Ш(P Щ Q) =ШQ Ъ ШP;

Вследствие законов ассоциативности скобки в выражениях, связанных отношениями дизъюнкции и конъюнкции могут быть опущены, при этом выражение F₁ Ъ F₂ Ъ…Ъ F_n называется дизъюнкцией формул F₁, F₂,…, F_n, а выражение F₁ Щ F₂ Щ…Щ F_n называется конъюнкцией формул F₁, F₂,…, F_n.

Определение 7. Литерал (литера) есть атом или отрицание атома.

Определение 8. Формула F находится в конъюнктивной нормальной форме тогда и только тогда, когда F имеет вид: F₁ Щ F₂ Щ…Щ F_n, n >=1, где каждая из F₁, F₂,…, F_n есть дизъюнкция литералов.

Определение 9. Формула F находится в дизъюнктивной нормальной форме тогда и только тогда, когда F имеет вид: F₁ Ъ F₂ Ъ…Ъ F_n, n >=1, где каждая из F₁, F₂,…, F_n есть конъюнкция литералов.

Теорема 1. Пусть даны формулы F₁, F₂,…, F_n и формула P. Тогда P есть логическое следствие F₁, F₂,…, F_n тогда и только тогда, когда формула ((F₁ Щ F₂ Щ…Щ F_n)®P) общезначима.

Теорема 2. Пусть даны формулы F₁, F₂,…, F_n и формула P. Тогда P есть логическое следствие F₁, F₂,…, F_n тогда и только тогда, когда формула (F₁ Щ F₂ Щ…Щ F_n ЩШP) противоречива.

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

Исчисление предикатов первого порядка.

В логике высказываний атом рассматривается как единое целое, его структура и состав не анализируется. Однако, есть много умозаключений, которые не могут быть представлены таким простым способом. Например, рассмотрим следующее умозаключение:

Каждый человек смертен.

Так как Конфуций человек, то он смертен.

Приведенное рассуждение интуитивно корректно, однако, если мы введем обозначения:

P: Каждый человек смертен,

Q: Конфуций – человек,

R: Конфуций смертен,

то R не есть логическое следствие P и Q в рамках логики высказываний.

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

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

1. Константы – это обычно строчные буквы a, b, c… или осмысленные имена объектов;

2. Переменные – это обычно строчные буквы x, y, z, …, возможно с индексами;

3. Функции – это обычно строчные буквы f, g, h,… или осмысленные слова из строчных букв;

4. Предикаты – это обычно прописные буквы P, Q, R … или осмысленные слова из прописных букв;

5. Логические связки: отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность;

6. Кванторы всеобщности и существования - ", $;

7. Открывающая и закрывающая скобка.

Всякая функция или предикатный символ имеет определенное число аргументов. Если функция f имеет n аргументов, то f называется n - местной функцией. Аналогично, если предикат P имеет n аргументов, то P называется n - местным предикатом.

Определение 10. Термы определяются рекурсивно следующим образом:

· Константа есть терм;

· Переменная есть терм;

· Если f есть n- местная функция и t₁, t₂,…,t_n – термы, то f (t₁, t₂,…,t_n) – терм;

· Никаких термов, кроме порожденных применением указанных выше правил, нет.

Определение 11. Предикат P(t₁, t₂,…,t_n) есть логическая функция, определенная не множестве термов t₁, t₂,…,t_n, при фиксированных значениях которых она превращается в высказывания со значением истина (И) или ложь(Л).

Определение 12. Если P – n- местный предикат и t₁, t₂,…,t_n – термы, то P(t₁, t₂,…,t_n) – атом.

Для построения формул в исчислении предикатов используются пять логических связок и два квантора: " - всеобщности и $- существования. Если x – переменная, то (" x) читается как «для всех x», «для каждого x», «для любого x», тогда как ($ x) читается как «существует x», «для некоторых x», «по крайней мере для одного x».

Пример 1: запишем следующие утверждения:

1. Каждое рациональное число есть вещественное число.

2. Существует число, которое является простым.

3. Для каждого числа x существует такое число y, что x<y.

Обозначим «x есть простое число» через P(x), «x есть рациональное число» через Q(x), «x есть вещественное число» через R(x) и «x меньше y» через МЕНЬШЕ (x, y).

Тогда указанные выше утверждения могут быть записаны соответственно выражениями:

1. ("x) (Q(x)® R(x)),

2. ($x) P(x),

3. ("x) ($y) МЕНЬШЕ (x, y).

Каждое из выражений 1, 2, 3 называется формулой. Прежде чем дать формальное определение формулы в логике предикатов, следует установить различие между связанными переменными и свободными переменными и определить область действия квантора, входящего в формулу, как ту формулу, к которой этот квантор применяется. Так, область действия квантора существования в выражении 3 есть МЕНЬШЕ (x, y), а область действия квантора всеобщности в выражении 3 есть ($y) МЕНЬШЕ (x, y).

Определение 13. Вхождение переменной x в формулу называется связанным тогда и только тогда, когда оно совпадает с вхождением в квантор (" x) или ($ y) или (и?) находится в области действия квантора. Вхождение переменной в формулу свободно тогда и только тогда, когда оно не является связанным.

Определение 14. Переменная свободна в формуле, если хотя бы одно ее вхождение в эту формулу свободно. Отметим, что переменная в формуле может быть свободной и связанной одновременно.

В формуле (" x) P(x,y) переменная x связана, так как оба вхождения x связаны, однако переменная y – свободна, так единственное вхождение y свободно.

Определение 15. Правильно построенные формулы логики первого порядка рекурсивно определяются следующим образом:

1. Атом есть формула.

2. Если F и G – формулы, то Ш(F), (F Ъ G), (F Щ G), (F ® G), (F «G) – формулы.

3. Если F – формула, а x – свободная переменная в F, то (" x) F и ($ x) F –формулы.

4. Формулы порождаются только конечным числом применений правил 1-3.

Определение 16. Терм t называется свободным для переменной x в формуле f, если ни x, ни другая произвольная переменная из t не находится в области действия никакого квантора "x или $x в f.

Пример2: переведем в формулу утверждение «Каждый человек смертен. Конфуций – человек, следовательно, Конфуций смертен».

Обозначим «x есть человек» через P(x), а «x смертен» через Q(x). Тогда утверждение «Каждый человек смертен» может быть представлено формулой (" x) (P(x)® Q(x)), утверждение «Конфуций – человек» формулой P(Конфуций) и «Конфуций смертен» формулой Q(Конфуций).

Утверждение в целом может быть представлено формулой

(" x) (P(x)® Q(x)) Щ P(Конфуций) ® Q(Конфуций).

Дата добавления: 2015-06-27