Лекции Просолупов

1 1 ... .

Если некоторая переменная совпадает с переменной , сложим коэффициенты по модулю 2. Полученный полином Жегалкина линеен. Следовательно,

( 1, ..., −1, +1, ..., , 1, ..., ) . Таким образом, [ ] = .

Замечание 45.4 . Тождественная функция ( ) = лежит в классе . Дизъюнкция ( ) = не лежит в . Таким образом, ̸= ? и ̸= 2.

Лемма 45.5 (О нелинейной функции). Пусть ( 1, ..., ) / . Тогда, подставляя в вместо аргументов константы, , , , и, возможно, навешивая отрицание над можно получить .

умаляя общности, положим

{1, 2} *

( 1, ..., ) =

=1 2 1,2( 3, ..., ) 1 1( 3, ..., ) 2 2( 3, ..., ) 0( 3, ..., ),

причем 3, ..., : 1,2( 3, ..., ) = 1. Действительно, такие 3, ..., существуют, поскольку, если бы 1,2( 3, ..., ) = 0, 3, ..., {0, 1}, то функция приняла бы вид

( 1, ..., ) = 1 1( 3, ..., ) 2 2( 3, ..., ) 0( 3, ..., ),

что противоречит нашему предположению, что {1, 2} * и ( *) = 1. Рассмотрим

( , ) = ( , , 3, ..., ) = 1( 3, ..., )2( 3, ..., ) 0( 3, ..., ) = .

Теперь определим ( , ), как ( , ) = ( , ) . Тогда

( , ) = (( )( ) ( ) ( ) ) = = = .

Таким образом, мы получили функцию ( , ) = , причем

( , ) = ( 2( 3, ..., ), 1( 3, ..., ), 3, ..., )1( 3, ..., ) 2( 3, ..., ) 0( 3, ..., ),

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

101

Пример 45.6 (Построение с помощью нелинейной функции). Пусть

( , , ) = ( ). Построим полином Жегалкина этой функции методом неопределенных коэффициентов.

( , , ) = 0 1 2 3 1,2 1,3 2,3 1,2,3 .

Таким образом ( , , ) = 1 и функция нелинейна.

Построим функцию ( , ) = . В нашем случае коэффициент при не равен нулю; выделим в полиноме Жегалкина переменные и .

( , , ) = 1 = · 1 · (1 ) 1

Тогда можно положить = 0 и в терминах леммы 45.5 получим, что = 1,

= 0, = 1 и

( , ) = ( , , 0) = ¬ ( , , 0)

Проверим, что соответствует конъюнкции:

( , ) = ( ( 0)) = = = .

§46. Критерий полноты системы функций

Итак, мы рассмотрели пять классов функций 0, 1, , , .

Каждый из этих классов функций замкнут и, как можно видеть из таблицы, ни один не совпадает с 2.

Теорема 46.1 (Теорема Поста). Для полноты системы функций 2

необходимо и достаточно, чтобы не лежал полностью ни в одном из классов

0, 1, , , :

̸0, ̸1, ̸ , ̸ , ̸ .

102

Доказательство. Необходимость. Если система функций лежит полностью в одном из классов { 0, 1, , , }, то, поскольку все эти классы замкнуты и не совпадают с 2, [ ] [ ] ̸= 2. Тогда система — не является полной.

Докажем достаточность. Пусть 0, 1, , , такие функции, что 0 / 0,1 / 1, / , / , / (некоторые из функций могут совпадать). Проведем доказательство в несколько этапов.

1) Покажем, что с помощью 0, 1, можно получить 0 и 1.

a) Пусть 0(1, ..., 1) = 1. Пусть ( ) = 0( , ..., ). Тогда (0) = (1) = 1. Значит

по лемме о несамодвойственной функции получаем константу 0 или 1 и с помощью

получаем вторую константу.

2)По лемме о немонотонной функции, подставляя константы в можно получить ¬ .

3)Используя , константы и ¬ , по лемме о нелинейной функции можно получить .

Так как {¬, } — полная система функций, то и система — полная.

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

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

таблице хотя бы одну строку, появится столбец не имеющий минуса.

Определение 46.3 . Пусть M — замкнутый класс функций. Пусть M. называется базисом класса M, если

103

1) [ ] = M;

2)Система {0, 1, , } полная, но базисом 2 не является. Базисом 2 будет

ееподсистема {1, , }.

104

Лекция 16. Исчисление высказываний

§47. Пример задачи логики высказываний

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

Простые высказывания:

= капиталовложения останутся постоянными;= возрастут правительственные расходы;= возрастет безработица;= налоги будут снижены.

На основе простых высказываний построим сложные высказывания:

= ( ),

= ¬ ,

= ( ) ¬ .

Здесь высказывание можно прочитать как "если капиталовложения

останутся постоянными, то возрастут правительственные расходы, или возрастет безработица". Аналогично можно читать и другие сложные высказывания.

Замечание 47.1 . Для определенности здесь и далее простые высказывания будем обозначать большими латинскими буквами , , ,..., а сложные высказывания

округлыми большими латинскими буквами , , ,...

Определение 47.2 . Здесь , , — пропозициональные буквы, , , —

пропозициональные формы, построенные из пропозициональных букв с помощью связок {¬, , , , ≡} по правилам построения формул алгебры логики.

Рассмотрим следующее рассуждение:

, , , — посылки

— заключение

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

105

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

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

согласуется с одним из интуитивных логических законов: исходя из ложных посылок можно вывести как истинное, так и ложное заключение.

Проверим, выполнима ли формула . Такую проверку для посылок нужно выполнять каждый раз.

( ( ))( )( ) =

=( )( )( ) =

=( )( ) =

=

==

Легко убедиться, что, например, на наборе значений = 1, = 1, = 1, = 0 полученное выражение обращается в единицу. Таким образом, —

выполнимая функция, т.е. посылки непротиворечивы.

Вычислим теперь значение выражения , воспользовавшись результатами предыдущих выкладок:

( ) = =

=· = ( )( ) =

==

=( ) = 1

Исследуемая формула оказалась тавтологией. Значит, высказывание действительно оказалось логическим следствием посылок , , и .

При этом мы нигде не обсуждаем истинность самих высказываний , , , ;

возможно они неверны. Тем не менее, если они истинны, то верным окажется и заключение.

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

, , . Если мы определим отличные значения для элементарных высказываний,

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

106

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

Определение 48.1 . Формальная теория — это совокупность четырех объектов:

1)Алфавит A — произвольное множество элементов, которые, в этом случае, называют символами.

2)Множество формул F — некоторое множество слов в алфавите A:

3)Множество аксиом B — некоторое множество формул: B F.

4)Множество правил вывода R — множество отношений на множестве формул:

F × F × · · · × F .

+1

Определение 48.2 . Пусть R — некоторое + 1-арное правило вывода. Если1, 2, ..., , +1 — формулы из F и ( 1, 2, ..., , +1) , то говорят, что +1 непосредственно выводима из 1, 2, ..., (или +1 непосредственное следствие 1, 2, ..., ) по правилу вывода .

Определение 48.3 . Вывод — это последовательность формул 1, 2, ..., , такая что для каждого {1, ..., } верно одно из двух:

a)B — аксиома, или

b)непосредственно выводима из формул 1 , 2 , ..., , 1 ≤ < , по

некоторому правилу вывода данной формальной теории.

Определение 48.4 . Говорят, что формула формальной теории является теоремой (выводима в формальной теории ), если для нее существует вывод 1,2, ..., = .

Пишут .

Определение 48.5 . Аксиоматическая теория — формальная теория, в которой существует алгоритм, позволяющий для любой формулы определить, является

ли аксиомой.

Определение 48.6 . Разрешимая теория — формальная теория, в которой существует алгоритм, позволяющий для любой формулы определить, является

ли теоремой.

Неразрешимая теория — теория не являющаяся разрешимой.

Определение 48.7 . Пусть F — некоторое множество формул теории . Формула выводима в формальной теории из множества посылок ( — следствие формул множества ), если для нее существует последовательность

107

формул 1, 2, ..., = , такая что для каждого {1, ..., } верно одно из трех:

a)B — аксиома,

b)— посылка, или

c)непосредственно выводима из формул 1 , 2 , ..., , 1 ≤ < , по

некоторому правилу вывода теории .

Такую последовательность формул будем называть выводом из посылок . Пишут .

Пример 48.8 . Формальная теория :

1)Алфавит: A = {|}.

2)Формулы — последовательности из символа | произвольной длины: F = A*

3)Аксиома: B = {||}.

4)Правило вывода: = {( , ) | — формула, = }.

Вывод:

1.|| — аксиома.

2.|||| — из строки 1 по правилу вывода .

3.|||||||| — из строки 2 по правилу вывода .

Таким образом, теоремами этой формальной теории являются последовательности из символа | длины 2 для любого N.

Формальная теория является аксиоматической и разрешимой.

§49. Формальная теория исчисление высказываний

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

1.Алфавит: { 1, 2, ..., , ..., ¬, , (, )}.

2.Формулы: 1) — формула, для любого N.

2)Если и — формулы, то ¬ и ( ) — формулы.

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

3.Аксиомы: Пусть , , — произвольные формулы. Тогда следующие

формулы являются аксиомами:

1 ( ( )), 2 (( ( )) (( ) ( ))),

3 ((¬ ¬ ) ((¬ ) )).

Замечание 49.1 . Три указанные формулы являются схемами аксиом: при подстановке в одну из схем произвольных формул теории мы получим аксиому.

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

3соответственно.

4.Правило вывода modus ponens (правило отделения):

MP = {( , ( ), ) | , F}.

108

То есть, если и произвольные формулы теории , то непосредственно выводима из формул и ( ) по правилу вывода modus ponens.

Замечание 49.2 . Модус поненс в логике называют модусом утверждающим или конструктивным. Существует похожий логический закон модус толленс (modus

tollens): из посылок и ¬ следует заключение ¬ . Модус толленс называют

модусом отрицающим или деструктивным.

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

а) из посылок и ; следует заключение б) из посылок и ¬ . следует заключение ¬

Пример 49.3 . Рассмотрим формализацию следующего рассуждения. “Если Вася баскетболист, то Вася высокий. Вася баскетболист. Следовательно Вася высокий”.

Обозначим через высказывание “Вася баскетболист” и через — “Вася высокий”. Тогда наше рассуждение будет иметь вид:

, .

Чтобы убедиться, что оно верно, проверим, является ли формула ( ) тавтологией.

( ) = ( ) = = =

= ( )( ) = = 1.

Теперь рассмотрим это рассуждение с точки зрения теории .

1)— посылка.

2)— посылка.

3)— MP к 1 и 2.

Следовательно, , .

Согласно определению 47.3, если формула получена по правилу вывода MP из предыдущих, формула является их логическим следствием. Таким образом, наше

рассуждение верно и с точки зрения формальной теории .

С другой стороны, если мы сформулируем наше рассуждение, как “Если Вася баскетболист, то Вася высокий. Вася высокий. Следовательно Вася баскетболист”, формула примет вид

, ,

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

( ) = (( ) ) = .

Очевидно, результат выкладок не является тавтологией.

109

Замечание 49.4 . В алфавите формальной теории нет символов , , ≡. Тем

не менее, мы можем использовать эти символы, как краткую форму записи в некоторых сложных выражениях:

( ) = (¬ ),

( ) = (¬( ¬)),

( ≡ ) = (( ) ( )) = (¬(( ) ¬( ))).

Для простоты иногда будем опускать внешние скобки в записи формул: вместо ( ) — писать .

110