Элементарный курс математической логики (стр. 3 )

Используя табл.2, получим в результате

■

Пример 7. Найти совершенную дизъюнктивную нормальную форму функции

Данная формула не содержит явным образом переменную x3. Следовательно, x3 является для данной функции несущественной переменной. Составим таблицу истинности для .

Таблица 8.

0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	1
1	0	1	0	0	1
1	1	0	1	1	1
1	1	1	1	1	1

Жирным шрифтом в табл.8 выделены наборы значений аргументов, на которых функция принимает значение 1. По этим наборам s1,s2,s3 составляются элементарные конъюнкции

Тогда в силу формулы (13) имеем

(14)

Формула (14) – искомая совершенная дизъюнктивная нормальная форма. ■

Обсудим результат, полученный в примере 7. Тот факт, что несущественная переменная x3 явным образом входит в СДНФ, указывает на наличие “лишних” операций в формуле (14). Используя свойства (5), проведем сокращения дизъюнктивной нормальной формы:

Помимо ожидаемого результата – исключения из формулы переменной x3, мы обнаружили, что переменная x2 также является несущественной. Установлена равносильность формул

Получим теперь результат, двойственный по отношению к теореме 2. Назовем элементарной дизъюнкцией ранга n переменных x1,…,xn выражение

(15)

при условии, что каждая переменная xi встречается в (15) в точности один раз. Величины – параметры, которые принимают значения из множества {0;1}.

В формуле (15) принято

Пусть теперь a1,…,an – произвольный фиксированный набор значений параметров . На основании правила де Моргана можно получить следующее равенство

Этот результат используется при доказательстве следующей теоремы.

Теорема 3. Любая логическая функция, отличная от константы 1, может быть представлена в виде

(16)

Действительно, по правилу двойного отрицания

Тогда в силу теоремы 2

и далее

что совпадает с формулой (16). Теорема 3 полностью доказана. ■

Выражение вида

которое присутствует в формуле (16), называется совершенной конъюнктивной нормальной формой (СКНФ) логической функции .

2.3. Функционально полные системы

Согласно теореме 2 любую логическую функцию за исключением константы 0 можно выразить через суперпозицию конъюнкции, дизъюнкции и отрицания в виде СДНФ. С учетом закона противоречия справедлива следующая теорема.

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

Утверждение теоремы 4 может быть получено также как следствие теоремы 3 и правила исключенного третьего: .

При этом говорят, что конъюнкция, дизъюнкция и отрицание образуют функционально полную систему .

В литературе используется общее название для трех этих функций – булевы функции. Формула, представляющая собой суперпозицию булевых функций называется булевой формулой. Используя данную терминологию, можно сформулировать теорему 4 так:

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

Пример 8. Представить булевой формулой функцию .

Таблица истинности данной функции содержится в табл.7. Как видно из этой таблицы, значение 1 достигается функцией на семи наборах значений аргументов, значение 0 – на одном наборе: Выберем в качестве булевой формулы для ее СКНФ. При этом функция выражается через единственную элементарную дизъюнкцию

■

Множество всех двузначных логических функций с определенными на нем операциями конъюнкции, дизъюнкции и отрицания называется булевой алгеброй логических функций. Подробное рассмотрение булевой алгебры выходит за рамки данного учебного пособия. Необходимою информацию по этому вопросу можно найти в книгах из рекомендованного списка литературы.

Помимо F0 можно построить другие функционально полные системы.

Пример 9. Доказать, что системы

являются функционально полными.

1) Рассмотрим правило де Моргана . Применив к левой и правой частям равенства операцию отрицания, получим и далее в силу закона двойного отрицания

. (17)

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

2) Рассмотрим правило де Моргана . Применив к левой и правой частям равенства операцию отрицания, получим и далее в силу закона двойного отрицания

. (18)

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

3) Используем функциональную полноту системы F2, которая доказана в п.2 данного примера, а также выражения для дизъюнкции и отрицания

(19)

Тогда любую логическую функцию можно представить суперпозицией функций из системы F2, а затем в полученной суперпозиции все конъюнкции и отрицания заменить выражением из формул (19). В результате данная произвольная логическая функция будет представлена суперпозицией единственной операции – стрелки Пирса. Это доказывает функциональную полноту системы F3. ■

Упражнения

2.1. Представить в СДНФ следующие логические функции:

1)

2)

3)

4)

2.2. Разложить по переменной p следующие логические функции:

1)

2)

3)

4)

2.3. Представить в СКНФ следующие логические функции:

1)

2)

3)

4)

2.4. Проверить, какие из следующих логических формул являются тавтологиями:

1)

2)

3)

4)

3. ПРИМЕНЕНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ

В ЛОГИКЕ ВЫСКАЗЫВАНИЙ

3.1. Элементарные и составные высказывания

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

Пример 10. Рассмотрим предложения

Про каждое из этих предложений можно определенно сказать, каким оно является: истинным или ложным. Следовательно, данные предложения являются высказываниями. Высказывания – истинные, – ложное.

Запишем этот результат в символьной форме: ■

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

Пример 11. Рассмотрим предложение

Данное предложение можно представить в виде . Здесь

Фрагменты данного предложения в свою очередь являются высказываниями. Очевидно, что – ложное высказывание и – ложное высказывание. Словесная форма “если…, то…” служит для передачи логического следования и соответствует импликации. Это позволяет представить предложение логической формулой Используя таблицу истинности для импликации, по установленным логическим значениям определяем логическое значение , так что данное предложение оказывается истинным высказыванием. ■

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

3.2. Тавтологии логики высказываний

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

Пример 12. Рассмотрим предложение

Это высказывание, которое можно представить в виде,

где . Формула реализует константу 1 в силу закона исключенного третьего. Так что высказывание является истинным независимо от того, лежит в действительности книга на столе или нет. ■

Вообще, формулы-тавтологии представляют собой схемы построения истинных высказываний независимо от истинности составляющих высказываний. При использовании тавтологии результат не зависит от содержания фрагментов предложения. Он может быть получен, даже если мы ничего не знаем про явления и объекты (предметную область), о которых говорится в высказывании. Еще более полезно то, некоторые из тавтологий представляют правильные способы логического вывода, которые от истинных посылок всегда приводят к истинным заключениям.

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

(20)

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

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

Теорема 5. Если формулы и являются тавтологиями, то формула также является тавтологией.

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

Теорема 5 известна в литературе под названиями: правило заключения, правило отделения, правило modus ponens [модус поненс].

Теорема 6. Если формула является тавтологией, то подстановка в эту формулу вместо переменных любых формул приводит к тавтологии вида. .

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

Теорема 6 известна, как правило подстановки.

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

Пример 13. На вопрос, кто из трех студентов присутствовал на занятии, был получен ответ: если третий присутствовал, то и второй присутствовал, но неверно, что, если первый присутствовал, то и второй присутствовал. При условии, что данный ответ правдивый, требуется определить, кто в действительности присутствовал на занятии?

Обозначим высказывания:

S1 – первый студент присутствовал на занятии,

S2 – второй студент присутствовал на занятии,

S3 – третий студент присутствовал на занятии.

Тогда условие задачи запишется в символической форме

.

Представим каждую импликацию в СКНФ. Получим:

.

Тогда

Последнее равенство выполняется только, при значениях То есть установлено, что первый студент присутствовал на занятии, а второй и третий – отсутствовали. ■

Упражнения

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

1)

2)

3)

4)

3.2. Даны высказывания

; ;

.

Сформулировать составные высказывания, соответствующие следующим формулам:

1) , 2) , 3) , 4) .

3.3. Определить, кто из четырех студентов сдал зачет, если известно, что:

1) если четвертый сдал, то и первый сдал;

2) если первый сдал, то второй сдал или четвертый не сдал;

3) если третий не сдал, то четвертый сдал, а второй не сдал;

4) если третий сдал, то и четвертый сдал.

4. ЛОГИКА ПРЕДИКАТОВ

4.1. Начальные понятия логики предикатов

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

Пример 14. Дано предложение

P(x): x>2, где xÎR. (21)

Предложение (21) содержит переменную величину x, которая принимает свое значение на R – множестве действительных чисел. Относительно x сделано утверждение x>2. Как только на место переменной будет подставлено определенное значение, возникает числовое неравеноство. Относительно числового неравенства мы можем судить, правильное оно или нет. Так что подстановка на место x какого-нибудь числового значения превращает (21) в высказывание. Подставляя разные значения переменной x, мы можем получить как истинное высказывание, так и ложное. Так что само предложение (21) не имеет однозначной оценки, следовательно, не является высказыванием. Однако, оно задает правило, по которому каждому действительному числу ставится в соответствие одно из логических значений 1 либо 0. Мы можем рассматривать P(x) как функцию

P(x): R → B, B={1,0}. ■

Определим теперь одноместный предикат, заданный на произвольном множестве M (предметной области) как функцию