Истинностные значения булевых формул

Говорят, что формула f(а) существенным образом зависит от переменной а, если f(0) f(1). Примерами таких функций являются : ab, (ab)c.

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

Формула называется выполнимой, если существует набор значений переменных формулы, при которых она истинна. Например, формула (ab)c истинна, если с – истина. Любая тождественно-истинная формула выполнима.

Формула называется невыполнимой, или противоречием, если она ложна при любых значениях входящих в неё переменных. Например, формула хх является невыполнимой. Конъюнкция двух различных конституэнт единицы – тождественно-ложная формула. Отрицание любой тавтологии – формула невыполнимая.

Формула называется опровержимой, если существует набор значений переменных, при которых она ложна. Например, формула (aÞb)Þc является опровержимой, т.к. она ложна при a=0, b=1, c=1.

Формулы А и В называются равносильными, если при любых значениях пропозициональных переменных они принимают равные значения. Логические законы связывают равносильные формулы.

Обычно формула является одновременно выполнимой и опровержимой, например, формула ab является истинной при а=1, и ложной при a=b=0.

Теорема. Если формула А(х₁, х₂,…, х_n), где х₁, х₂,…, х_n – пропозициональные переменные, тавтология, то формула А(t₁, t₂,…, t_n), где t₁, t₂,…, t_n – некоторые формулы, так же являются тавтологией.

Например, - тавтология, поэтому формула на основании теоремы так же является тавтологией.

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

Формальные теории

Теория Т – множество аксиом {A_i} и множество правил вывода S.

Вывод формулы В в теории Т – последовательность формул F₁, F₂,…, F_n=B, такая, что каждая формула F_i или одна из множества аксиом {A_i}, или выводима из некоторого подмножества множества { F₁, F₂,…, F_i-1 } по одному из правил вывода.

Теорема теории Т – формула, выводимая в этой теории.

Рассмотрение исчисления высказываний будет проведено позднее.

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

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

Логический вывод в исчислении предикатов используется в различных областях, для его применения необходимо, чтобы предметная область была описана формально, на языке исчисления предикатов. Ярким примером применения логического вывода является метод Шерлока Холмса (где использовался вывод с неявными посылками), в правилах дорожного движения (определить транспортное средство, имеющее первоочередное право проезда), геометрия, построенная как аксиоматическая теория. Наиболее актуальной областью применения логического вывода в наше время являются базы данных, где логический вывод применяется для проверки непротиворечивости ограничений целостности, проверки соответствия запроса ограничениям целостности, проверке целостности базы данных.

Примером, часто иллюстрирующим логический вывод, является рассуждение:

«Все люди смертны. Сократ – человек, следовательно, Сократ смертен.»

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

Соглашение о правилах записи суждений.

1. Речь идёт о некоторых предметах (Сократ, человек,…). Если речь идёт о конкретных предметах, то им сопоставляются индивидные (предметные) константы. Обозначать их будем строчными буквами начала латинского алфавита с индексами или без них, например, a,b,c,…a₁,a₂,… Когда речь идёт о предметах вообще, им сопоставляются индивидные переменные, которые обозначаем строчными буквами из конца латинского алфавита с индексами или без них: x, y, z,…, x₁,x₂,…

2. Предикатные переменные соответствуют суждениям об объектах, имеющим значение «истина» или «ложь». Предикатные переменные обозначаются прописными латинскими буквами с индексами или без них (P, S,Q,…R,…).

Формально:

В предметном мире A используются функциональные буквы , где k – число аргументов, нижний индекс используется для отличения одной функции от другой (обозначающие отображения A^kA). Объекты, построенные из индивидных констант и переменных и функциональных букв – термы.

Определения:

Терм:

1. Любая индивидная переменная и константа – терм.

2. Если - функциональная буква, t₁,…,t_k – термы, то ( t₁,…,t_k) – терм.

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

Например, …

Если - предикатная буква, t₁,…,t_k - термы, то ( t₁,…,t_k) - элементарная формула.

Формула:

1. Элементарная формула – формула.

2. Если А и В – формулы, у- предметная переменная, то , (АВ), (АВ), (АВ), (АВ), у А, у А – формулы.

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

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

Для исключения лишних скобок принято соглашение о силе связок: сильнее всего связывают кванторы, отрицание – следующее по силе, затем, в порядке убывания силы: , , , . То есть, получается, что область действия квантора – элементарная формула, или формула в скобках, следующая за квантором, или охватывает область действия квантора, следующего за данным.

Пример.

Вхождение переменной х в формулу называется связанным, если х – переменная квантора х или х, или находится в области действия квантора х или х. В противном случае переменная свободна в формуле.

Алфавитным вариантом формулы А называется формула, полученная из А переименованием свободных переменных (пример)

Иногда, не обращая внимания на свободу-связанность переменной в формуле, и независимо от вхождения переменной x_i в формулу, будем писать A(x₁,x₂,…,x_n), чтобы обозначить A(t₁,t₂,…,t_n) подстановку термов t₁,t₂,…,t_n вместо переменных x₁,x₂,…,x_n в формулу А.

Формула называется замкнутой, если она не содержит свободных переменных.

Ограниченные кванторы.

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

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

.

Выражения с ограниченными кванторами могут быть заменены на обычные формулы исчисления предикатов по правилам:

В самом деле, утверждается, что все объекты, обладающие свойством Р, обладают свойством Q. Это то же самое, «если объект обладает свойством Р, то он обладает свойством Q», что и отражается в приведённой эквивалентности.

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