Дискретно-непрерывная математика (стр. 6 )

Возникает вопрос, какие истинностные функции соответст­вуют нашим логическим связкам?

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

Отсюда, например, следует, что высказываниеложно

тогда и только тогда, когда (т. т.т., когда) р истинно и q ложно. Приведенные выше таблицы называются истинностными таблицами, а определенные посредством их пропозициональные связки называются классическими связками.

Легко определить, сколько имеется различных классических связок. Число различных строк в таблице для истинностной функ­ции с m аргументами равно 2т и на каждой из них значение функ­ции можно задать двумя способами: 1 или 0. Поэтому число таких функций составляет 2 в степени 2т . Отсюда, например, число од­номестных связок равно 4, а число двухместных связок равно 16.

Каждая формула логики высказываний реализует некоторую истинностную функцию, которая графически может быть представлена истинностной таблицей. Другими словами, каждая формула может быть представлена как функция, у которой как переменные, так и сама функция, принимают значения из множества {0, 1}. Такие функции называются булевыми функциями в честь одного из создателей символической логики Дж. Буля (1815-1864).

1.2. Законы логики высказываний

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

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

являются тавтологиями. Законы, выражаемые этими формулами, называются соответственно законом тождества, законом исклю­ченного третьего и законом (не)противоречия и были сформулированы уже Аристотелем. Использование этих законов в качестве ограничений на допустимые способы рассуждений привело к тому, что они были названы основными законами мышления. Наиболее распространенной формулировкой закона исключенного третьего является следующая: одно из утверждений р или не-р должно быть истинным. Эта формулировка получила в схоластической логике название tertium n'on datur. Закон непротиворечия формулируется следующим образом: два взаимно противоречащих высказывания не могут быть одновременно истинными. Последний закон формулируется у Аристотеля прежде всего как универсальный принцип бытия, наиболее достоверный из всех начал. Однако уже на заре XX в. еще до того, как окончательно оформилась классическая логика, оба эти закона подверглись серьезной критике, что положило начало развитию неклассических логик. В связи с трехзначной логикой Лукасевича мы к этим законам ещё вернемся, а сейчас дополним список законов классической логики:

(4) (закон двойного отрицания)

(5) (закон контрапозгщии)

(6)- (закон Дунса Скота).

Особое место среди законов занимают чисто импликативные тавтологии:

(7) (закон утверждения консеквента)

(8)

(закон самодистрибутивности)

(9)

(закон сильной транзитивности)

(10) (закон сокращения)

(11) (закон перестановки)

(12)' (закон Пирса).

Точно так же выделяются формулы, которые принимают значение 0 независимо от того, какие значения принимают входящие в нее пропозициональные переменные. Такие формулы называются противоречиями (тождественно-ложными форму­лами). Примерами противоречий являются следующие формулы:

р р, p≡ p.

И вообще, из свойств связки отрицания следует, что отрицание тавтологии есть противоречие.

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

Приведем некоторые важные факты о тавтологиях настолько общих, что они лежат в основании правил вывода: modus ponens (отделения), подстановки и эквивалентной замены,

1. Если А и есть тавтологии, то В - тавтология.

2. Еели р переменная, то из А следует где есть формула, являющаяся результатом подстановки формулы В вместо каждого вхождения переменной р в А.

3. Если А ≡ В есть тавтология, то С(А) ≡ С(В) тоже тавтология, где С(А) — формула, содержащая некоторую формулу А в качестве своей составной части, и С(В) - формула, полученная из С(А) заменой этой составляющей А на формулу В.

1.3. Функциональная полнота. СДНФ

Будем называть формулы А и В эквивалентными (равносильными), если формула А ≡ В есть тавтология. Очевидно, что. если формулы А и В эквивалентны, то сопоставленные им истинностные таблицы совпадают, т. е. реализуют одну и ту же булеву функцию,

Назовем систему пропозициональных связок полной, если всякая иртинностная функция представима некоторой формулой, в которую входят только связки из системы т. е. посредством такой системы можно выразить все истинностные функции (в данном случае, все булевы функции). Используя свойства логической эквивалентности, можно показать, что в классической логике каждая логическая связка может быть определена в терминах т. е. система пропозициональных связок является функционально полной. Более точно, для каждой истинностной функции * можно найти такую формулу С, использующую только связки что истинностные таблицы для * и С одни те же.

Теорема о функциональной полноте. В классической логике высказываний каждая истинностно-функциональная связка может быть определена в терминах.

Отметим некоторые эквивалентности, показывающие взаимо­выразимость одних связок через другие:

Тогда системы связок являются

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

Обратим внимание, что посредством правила замены можно преобразовывать формулы, получая другие, им эквивалентные, в более простые (содержащие меньше пропозициональных связок и переменных). Также обратим внимание, что некоторые эквивалент­ности выражают основные свойства пропозициональных связок. Например, эквивалентности выражают коммутативный закон связок конъюнкции и дизъюнкции.

Важно то, что для решения определенного рода задач, например, задач о функциональной полноте или разрешимости, всегда можно привести формулу к некоторому каноническому виду, называемому нормальной формой. Существует несколько "нормальных форм" формул логики высказываний: Вначале рассмотрим совершенную дизъюнктивную нормальную форму (СДНФ).

Для пропозициональных переменных р1, ..., рп, входящих в формулу F, будем называть элементарной конъюнкцией

в которой Аі есть рі или pі. Формула находится в СДНФ, если она имеет вид дизъюнкции где каждое Bj является элементарной конъюнкцией переменных р1, ..., рп. Например, СДНФ для формулы