Министерство образования и науки

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

Московский государственный институт электроники и математики

(Технический университет)

Кафедра «Вычислительные

системы и сети»

Методические указания к самостоятельным (домашней и контрольной) работам по курсу

«Математическая логика и теория алгоритмов»

Москва 2008

Учебное издание

Математическая логика и теория алгоритмов

Составитель: доц., канд. тех. наук Л.Е.Захарова

УДК 519.1

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

Математическая логика и теория алгоритмов: Метод. указания к самостоятельным (домашней и контрольной) работам/ Моск. Гос. ин-т электроники и математики; Сост. Л.Е. Захарова. М., 2008. 23 с.

Ил. 1. Библиогр.: 3 назв.

Isbn 5-94506-100-х Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул

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

1). АВВА коммутативность

2). ААА идемпотентность

3). А(ВС)(АВ)С ассоциативность

4). АВВА коммутативность

5). ААА идемпотентность

6). А(ВС)(АВ)С ассоциативность

7) А(ВС)(АВ)(АС) дистрибутивностьотносительно

8) А(ВС)(АВ)(АС) дистрибутивностьотносительно

9). А(АВ)А первый закон поглощения

10). А(АВ)А второй закон поглощения

11). АА снятие двойного отрицания

12). (АВ)АВ первый закон Моргана

13). (АВ)АВ второй закон Моргана

14). А(АВ)(АВ) первая формула расщепления

15). А(АВ)(АВ) вторая формула расщепления

Следующие равносильности выражают одни логические символы через другие:

16). А~В(АВ)(ВА)(АВ)(АВ)

17). АВАВ(АВ)

18). АВАВ(АВ)

19). АВ(АВ) (АВ)

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

1). АА

2). АА

3). А(ВА)

4). (АВ((ВС)(АС)) цепное рассуждение

5). (А(ВС))((АВ)(АС))

6). АВА; АВВ

7). А(В(АВ))

8). А(АВ); В(АВ)

9). (ВА)((ВА)В)

10). ((АВ)А)А закон Пирса

При доказательстве эквивалентностей или равносильностей надо либо правую формулу равносильными преобразованиями свести к левой, либо левую к правой, либо обе к какой-то одной, третьей формуле. Если требуется доказать тождественную истинность формулы, то её надо равносильными преобразованиями свести к вышеизложенным тождествам. Если заданий несколько, то не более половины можно выполнить с помощью таблицы истинности. Например, докажем девятую равносильность: А(АВ)(АА)(АВ)А(АВ)А. Здесь использованы восьмая, вторая и десятая равносильности.

Логические символы иназывают двойственными друг другу. Рассмотрим формулы, содержащие только эти логические символы и инверсию. Формула Адвойственна формуле А, если она получена из А одновременной заменойина двойственные.

Система булевых функций называется полной, если любая булева функция может быть выражена через функции системы с помощью суперпозиций. Например, система из трёх функций {,,} является полной. Если система функций полная и любая из функций этой системы может быть выражена с помощью суперпозиций через функции второй системы функций, то эта вторая система функций тоже является полной. В общем случае для проверки полноты системы функций надо составлять таблицу Поста. Она нужна для проверки теоремы Поста для этой системы: Если система полная, то для каждого из функционально замкнутых классовT, T,S, L и M найдётся функция из системы, не принадлежащая этому классу. Например, для системы {,,} таблица Поста имеет вид:

Функция	T	T	S	L	M
	+	+	-	-	+
	+	+	-	-	+
	-	-	+	+	-

Эта система функций является полной, так как в каждом столбце таблицы присутствует «-». Функция принадлежит T, если во всех нулях она равна нулю, и принадлежит T, если во всех единицах она равна единице. Функцияf(x,y, … ,w) самодвойственна, если f(x,y, … ,w)= f(x, y, … , w). Функция линейна, если линеен её полином Жигалкина. Для инверсии полином Жигалкина имеет вид: x+1=x, он линеен и «+» - это сложение по модулю два. Для дизъюнкции: xy=xy+x+y, он не линеен и xy – это xy, это и есть нелинейность. Монотонная функции не должна упасть на возросшем наборе переменных. Набор переменных возрос, если все переменные или увеличились, или не изменились. Система функций независима, если ни какая функция из системы не может быть выражена с помощью суперпозиций через остальные функции системы. Система {,} независима, так какT,T,L, L. Система {,,} зависима, смотри выше законы Моргана.

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Формулу называют элементарной конъюнкцией, если она является конъюнкцией (может быть и одночленной) переменных и отрицаний переменных: xy, xyz. Формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (может быть и одночленной) элементарных конъюнкций: (xy) (xyz). Формула находится в Совершенной ДНФ (СДНФ), если каждый её дизъюнктивный член содержит по одному разу в прямом или инверсном виде все переменные формулы , и все её дизъюнктивные члены попарно различны: (xyz) (xyz) (xyz). Аналогично определяются элементарная дизъюнкция, КНФ и СКНФ. Приводить формулы к их нормальным формам надо используя равносильные преобразования. Для приведения к совершенным формам можно использовать таблицы истинности формул: пусть f(x,y,z)=(xz)(yz), СДНФ получается из единиц функции, а СКНФ – из нулей. При получении СДНФ нули переменных переходят в их инверсии: (xyz)(xyz)(xyz)(xyz), здесь элементарные конъюнкции получены последовательно из наборов переменных (001), (100), (101) и (110). При получении СКНФ единицы переменных переходят в их инверсии.

Минимизация проводится в классе ДНФ методом минимизирующих карт. Функция должна быть задана её таблицей истинности или её СДНФ. Минимизирующая карта имеет 2строк, гдеn – число переменных функции, и на единицу меньше столбцов. Например, для n=3:

x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz

Использование карты основано на следующем: если какая то конъюнкция последнего столбца карты не входит в СДНФ функции, то все конъюнкции этой строки не входят ни в одну ДНФ функции. Возьмём функцию f(x,y,z)=(xz)(yz) с таблицей истинности, представленной выше. Далее убираем из карты строки, соответствующие конъюнкциям, не вошедшим в СДНФ функции:

x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz
x	y	z	xy	xz	yz	xyz

Вычеркнутые в этих строках конъюнкции убираем во всех остальных строках карты. В каждой строке оставляем конъюнкции с наименьшим числом сомножителей:

					yz
			xy	xz
			xy		yz
				xz

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