Дискретная математика для программистов

Размещено на http://www.allbest.ru/

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1. БУЛЕВЫ ФУНКЦИИ

1.1 Определение булевых функций

1.2 Построение СНДФ, СНКФ и СНПФ. Минимизация

1.3 Реализация метода Квайна - Мак-Класки

1.4 Замкнутые классы. Полнота. Теорема Поста

1.5 Моделирование релейно-контактных схем

1.6 Моделирование сумматоров

2. ОСНОВНЫЕ ПОЛОЖЕНИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

2.2 Исчисление высказываний

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

2.4 Приложение исчисления предикатов к аналитической геометрии

3. ВЫЧИСЛИМОСТЬ

3.1 Неформальное определение алгоритма. Примеры

3.2 МНР-вычислимые функции

3.3 Рекурсия

3.4 Вычислимость по Тьюрингу

4. КОНЕЧНЫЕ АВТОМАТЫ

4.1 Основные определения и способы задания

4.2 Эквивалентность автоматов. Минимизация

4.3 Автоматы Мили и Мура. Размеченные графы

4.4 Автоматные языки

4.5 Возможности автоматов

5. НЕКОТОРЫЕ КЛАССИЧЕСКИЕ АЛГОРИТМЫ

5.1 Алгоритмы сортировки и их классификация

5.2 Поиск

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ВВЕДЕНИЕ

Математическая логика связана с классической, которая, в свою очередь, происходит от житейской. Центральные понятия: высказывание; истина и ложь; составное высказывание; равносильность высказываний. Первая попытка систематизации осуществлена Аристотелем. Логика Аристотеля является классической и относится к гуманитарному циклу наук. С ее помощью можно строить защиту в суде, но невозможно сконструировать электрическую, релейную или логическую схему.

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

Простые высказывания как элементы математической логики называются пропозициональными переменными, обозначаются буквами и принимают истинностные значения «И» или «Л».

Составные высказывания строятся из простых с помощью логических связок. Обычно рассматривают хорошо знакомые «И», «ИЛИ», «НЕ», а также «СЛЕДОВАТЕЛЬНО», «исключающее ИЛИ».

Связки аналитически задаются таблицами истинности:

А	B	A	AB	AB	AB	AB
И	И	Л	И	И	И	Л
Л	И	И	Л	И	И	И
И	Л	Л	Л	И	Л	И
Л	Л	И	Л	Л	И	Л

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

С помощью логических связок и пропозициональных переменных строятся формулы. Формулы принимают значения «И» или «Л» при конкретных значениях входящих в нее переменных.

Если при ЛЮБЫХ значениях истинности переменных формула истинна, то она называется тавтологией (или общезначимой). Если при любых значениях переменных формула ложна, то она называется невыполнимой (или является противоречием).

Для обозначения логического значения, которое принимает переменная (или формула), применим следующее: I(A).

Основная тавтология -

I(AA) И

Основное противоречие -

I(AA) Л

булевая функция логика вычислимость алгоритм

В данном учебном пособии рассматриваются в основном практически важные задачи и проблемы, которые могут быть решены с помощью алгоритмов. Точное определение понятия «алгоритм» достаточно противоречиво, однако практически все задачи математики решаются (если решения имеются) с помощью алгоритмов, понимаемых на интуитивном уровне.

К некоторым разделам пособия приведены варианты задач для самостоятельного решения. Задачи разделены на две группы. Одну из них представляют задачи типа контрольных вопросов, ответы на которые могут быть получены без применения ЭВМ. Вторая группа состоит из задач, решить которые без применения специальных вычислительных средств затруднительно (или невозможно).

1. БУЛЕВЫ ФУНКЦИИ

1.1 Определение булевых функций

Булевой функцией переменных будем называть однозначное отображение пространства , которое является прямым произведением пространств , состоящих из двух элементов, в пространство . Один из элементов будем обозначать Ш (или «ложь», «Л», «false»), другой - 1 (или «истина», «И», «true»). Пространство аргументов содержит элементов, каждый из которых записывается в виде -мерного вектора . Общее количество различных булевых функций - .

Среди булевых функций выделяются так называемая тавтология - функция, равная единице при любом наборе аргументов, и противоречие - функция, принимающая значение Ш при любом наборе аргументов. Отрицанием истины считается ложь, и наоборот: 10, 01. Отрицание функции - это такая функция , которая для любого набора аргументов принимает значение, противоположное соответствующему значению .

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

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

Перечень булевых функций двух переменных приведен в табл. 1.1.

Таблица 1.1 Булевы функции

X1	0	1	0	1	F	Обозначение	Название
X2	0	0	1	1
	0	0	0	0	0	Ш	Противоречие
	0	0	0	1	X1X2	, «.»,	Конъюнкция
	0	0	1	0	X2\ X1	\	Разность
	0	0	1	1	X2		Проекция Р2 (X1 , X2 ) = X2
	0	1	0	0	X1 \ X2		Разность
	0	1	0	1	X1		Проекция Р1 (X1 , X2 ) = X1
	0	1	1	0	X1 \ X2 X1 \ X2	?, xor, +	Симметричная разность, сложение по модулю 2
	0	1	1	1	X1X2	, + , or	Дизъюнкция
	1	0	0	0	(X1X2)		Стрелка Пирса (польский штрих)
	1	0	0	1	X1 X2	, ,	Эквивалентность
	1	0	1	0	X1		Отрицание X1
	1	0	1	1	X1 X2 X1X2		Импликация
	1	1	0	0	X2		Отрицание X2
	1	1	0	1	X2 X1 X2X1		Импликация
	1	1	1	0	(X1X2)		Штрих Шеффера
	1	1	1	1	1	I	Тавтология

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

- коммутативные законы:

, ;

- ассоциативные законы:

, ;

- дистрибутивные законы:

, ;

- законы идемпотентности:

, ;

- закон двойного отрицания

;

- законы Де Моргана:

, ;

- законы поглощения:

, .

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

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

Сопоставим с элементами множества М высказывания, с операциями сложения - дизъюнкцию, с операциями умножения - конъюнкцию, со знаком отрицания - отрицание высказывания, со знаками эквивалентности - равенства. В таком случае обнаружится, что алгебра логики является интерпретацией булевой алгебры. Роль истины играет единица (1), лжи - ноль (0):

, , , .

Еще одна интерпретация булевой алгебры - множества с операциями объединения, пересечения и дополнения. Имеются и другие интерпретации, например релейные схемы.

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

С отрицанием величины он сопоставил арифметическую разность , с конъюнкцией - арифметическое выражение , а с дизъюнкцией - арифметическое выражение

Данные операции даже использовались как эквиваленты логических операций в первых ЭВМ.

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

Контрольные задания

1. Максимально упростить выражение своего варианта, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравнить упрощенное выражение с исходным:

(a(шdb))(( шa( шbd))c) шc(a(b шd)),

((ac)(ad))(((c(cb)) шc) шa),

( шbd)(( шdc)(ac)( шd шc)(a шc))(bd),

(a шc)( шa шb)( шbc)( шab)(bc),

(ac)((b шd)( шa шd)(db)( шad))(a шc),

(( шb шc)(ab))(d шc)((( шb шa)c)(ab)),

(a шc)( шa шb)(bc)( шab)(c шb),

((a(c(bc))) ш(cd)(c шd))(c( шd шc)d),

((a шa)( шb шd)( шb шc)( шcd))(( шbc)(cd)),

(a шc)(( шad)(bd)( шa шd)(b шd))(ac),

((d шc)( шd шb)(c шb))(( шdb)(cb))( шaa),

(( шc шd)(bc))( шa шd)((( шc шb)d)(cb)),

((ab)( шbcd)( шa шbcd) шb шcd,

((ab)(a шb))(( шab)(c шd)( шa шb)(dc)),

(( шbc)( шcd) шa)( шab шcd) ш(cd)a,

((bc)(d( шb шc)))( шd шa)((cb)( шd шc)),

(bd)((c шd)(ac)( шd шc)(a шc))( шbd),

(( шcd)(da))((b шb)( шc шa)( шc шd)( шda)),

(a шd)((( шc шb)d)(cb))(( шd шc)(cb)),

(((d(dc)) шd) шb)((bd)(ba)),

(( шb( шca))d)) шd(b(c шa))(b( шac)),

((c шa)( шa шb)(ac)( шba))(b шd)(bd),

(d( шa шd)a)((b(d(dc))) ш(ca)(d шa)),

( шc шb)(dc)( шbс)(d шc)(b шd).

Пример. ( шc шb)(dc)( шbc)(d шc)(b шd):

( шc шb)( шbc)= шb,

(dc)(d шc)= d,

d(b шd)= (bd)(d шd)= (bd)I= bd,

шbd(b шd)= шbbd= Id= I.

2. Установить эквивалентность левой и правой частей следующих логических выражений: 1 lab

((a|b)|(a~b))|((c+d)>(d/c))=((b>c)>(a/c))v((a|d)|(d> шb)),

((a шc)v(b/c))((a|d)/(bd))=((a|b)|(a+ шb))>((c+d)(d>c)),

((avb)(a+b))/((c/d)v(c~d))=((c>a)(c>b)) >((avd)(bvd)),

((a~b)/(avb))v((c~d)v(c/d))=((c/a)v(c/b))|((avd)v(bvd)),

((ab)(a+b))/((d/c)v(d~c))=((a>c)(b>c)) >((a|d)|(b|d)),

((ab)/(a+b))((c/d)v(c~d))=((c/a)v(c/b))((ad)/(bvd)),

((d>b)>( шc/b))v((ca)|(d>a))=(( шc|d)|(c+d))|((a~b)>( шa/b)),

((a|b)/( шa+ шb))((d/c)v(c~d))=(( шav шd)v(b/ шd))((a>c)/(b/c)),

((c/a)(c~a))/((d/b)v(d~b))=((ab)(c>b))>((d/a)(cd)),

((c~b)/(bvc))v(( шa~ шd)v(a/d))=((bvd)v(cvd))|((a/b)v(a/c)),

((a/d)(a~d))/((b/c)v(b~c))=((b>d)(a|b))>((cd)|(a>c)),

((bvd)v(cvd))((a>b)/(a/c))=((bc)/(b+c))((a/d)v(a~d)),

((c>d)|(c+d))|((a~b)>(ab))=((a> шc)>(a/d))v((b>d)|(b> шc)),

((bd)v(bc))((d>a)/(c/a))=((c|d)|( шc~ шd))>((a+b)(b>a)),

((d/a)(d~a))/((c/b)v( шc+b))=((ab)(d>b))>((cd)(c/a)),

((c>d)/(c~d))((ab)v(a+b))=((bc)v(b/d))((a|c)/(a/d)),

(( шc>b)>(dvb))v((a>d)|(a>c))=((cd)|(c~d))|(( шa+ шb)>(a/b)),

((ac)v(b/ шa))((c>d)/(b/d))=((b|c)|(b~c))>((a+d)(a>d)),

((bv шd)( шb+d))/((a/c)v(a~c))=(( шc>b)(d>c)) >((a/b)(ad)),

((da)v(bd))|((a/c)v(b/c))=((a+ шb)/(ba))v(( шc~ шd)v(d/c)),

((avb)( шa~b))/((c/d)v(c~d))=(( шa>d)( шd>b))>((c>a)|(c>b)),

((c>a)/(a+ шc))((d/b)v(b~d))=((avb)v(c/b))((d>a)/(cd)),

((c| шb)|(c~ шb))|(( шa+ шd)>( шa/ шd))=((c> шd)>( шb/ шd))v

v(( шb| шa)|( шa>c)),

((cv шb)(c+ шb))/(( шd/ шa)v( шd~ шa))=(( шd> шb)( шd>c))>

> (( шb? шa)(cv шa)).

Пример основных фрагментов программы:

/ frazn, + xor, or, and, fimp, fsp,

| fsh, ~, = feqv

- логические функции и их идентификаторы;

function fsp(x,y:boolean): boolean;

begin fsp:=(not x) and (not y); end;

function feqv(x,y:boolean): boolean;

begin feqv:=(not x) and (not y) or x and y; end;

function frazn(x,y:boolean): boolean;

begin frazn:=x and (not y); end;

function fimp(x,y:boolean): boolean;

begin fimp:=(not x) or y; end;

begin

for a:=false to true do

for b:=false to true do

for c:=false to true do

for d:=false to true do begin

m1:=fsp(c,not b); m2:=c xor (not b); m3:=frazn(not d,not a); m4:=feqv(not d,not a); m5:=m1 or m2; m6:=fsp(m3,m4);

f1:=frazn(m5,m6);

n1:=fimp(not d,not b); n2:=fimp(not d,c); n3:=fsp(not b,not a);

n4:=fsp(c,not a); n5:=n1 and n2; n6:=n3 or n4;

f2:=fimp(n5,n6);

fsrav:=feqv(f1,f2);

write('| ');

if a then write('1') else write('0');

if b then write(' 1') else write(' 0');

if c then write(' 1') else write(' 0');

if d then write(' 1') else write(' 0');

write(' | ');

if f1 then write(' 1') else write(' 0');

write(' | ');

if f2 then write(' 1') else write(' 0');

write(' | ');

if fsrav then write(' 1') else write(' 0');

writeln(' | ');

end;

readln;

end.

Результат работы программы - таблица истинности:

1.2 Построение СНДФ, СНКФ и СНПФ. Минимизация

Рассмотрим некоторую булеву функцию, заданную формулой. Для составления ее таблицы истинности достаточно в цикле перебрать все значения аргументов и вычислить значения, принимаемые в этих наборах. Результат можно представить в виде таблицы. Шапкой таблицы являются наборы аргументов в виде векторов-столбцов; в строках выписаны значения функции в этих наборах. Альтернативой является транспонированная таблица.

Пример:



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

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

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

- для каждой строки, отвечающей истинности функции, выписывается конъюнкция, содержащая все независимые переменные, причем с нулем сопоставляется отрицание, и такие конъюнкции называются конституэнтами;

- конституэнты объединяются операциями дизъюнкции.

В данном примере

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

Если ограничиться строками, отвечающими истинности функции, то СНДФ-заданную функцию можно представить в виде матрицы, содержащей строки в количестве размерности пространства аргументов, а в качестве столбцов - наборы аргументов, соответствующих истинности заданной функции:

.

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

.

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

.

Под представлением булевых функций в виде совершенной нормальной полиномиальной формы (СНПФ) подразумевается представление функции в базисе (1, Ш, +, ):

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

Пример.

.

Рассмотрим набор аргументов

:

.

Далее

;

;

;



;

;

;

.

Это и есть СНПФ для заданной функции.

Можно также воспользоваться соотношениями

.

Они позволяют перейти от базиса (, , ) к базису (1, Ш, +, ).

1.3 Реализация метода Квайна - Мак-Класки

С помощью этого метода строят тупиковые НДФ (нормальные дизъюнктивные формы) и из множества тупиковых выбирают минимальные НДФ.

Основой алгоритма являются следующие эквивалентности:

;

;

.

Первая часть алгоритма:

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

2. После склеивания возможно появление элементарных одинаковых конъюнкций. Лишние нужно убрать.

3. Если дальнейшие склеивания неосуществимы, то переход к п. 4, иначе - к п. 1.

В результате приходят к некоторой сокращенной нормальной дизъюнктивной форме.

Вторая часть алгоритма (решение задачи о минимальном покрытии):

4. Рассматривают каждую элементарную конъюнкцию из полученной формулы и проверяют её вхождение в отдельные слагаемые исходной СНДФ.

5. Среди полученных элементарных конъюнкций могут оказаться и лишние. Их нужно отбросить.

В результате получают тупиковые формы, реализующие минимальное покрытие. Их может оказаться несколько. Минимальная НДФ является одной из тупиковых.

Замечания:

- данный алгоритм неизбежно включает в себя прямой перебор;

- алгоритм является NP-сложным (с ростом размерности сложность возрастает быстрее любой степени размерности);

- дальнейшее упрощение можно осуществлять, отказавшись от требования нормальности.

Пример. Требуется минимизировать булеву функцию, заданную в совершенной нормальной дизъюнктивной форме:



.

Сопоставим с этой функцией булеву матрицу

.

Рассмотрим первый и второй столбцы. Запишем их дизъюнкцию и вынесем общие множители:

.

Формально это действие сводится к тому, что переменная X2 подвергается удалению. Сопоставим с отсутствием этой переменной символ 2 (возможно использование и других символов):

.

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

(0,1) 2; (1,0) 2; (0,2) 2; (2,0) 2;

(1, 2) 2; (2, 1) 2; (2, 2) 2.

Результаты склеивания заносим в качестве столбцов в новую матрицу. Некоторые столбцы не склеиваются с другими; записываем такие столбцы в новую матрицу без изменений. Чтобы учесть наличие несклеиваемых столбцов, те из них, которые участвуют в склейках, снабжаем дополнительным символом, например «+»:

+	+	+	+	+	+	+	+	+	+	+	+
1	1	0	1	0	1	0	1	0	1	1	1
0	1	0	0	1	1	0	0	1	1	0	1
0	0	1	1	1	1	0	0	0	0	1	1
0	0	0	0	0	0	1	1	1	1	1	1

F =

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

1,2	1,4	1,8	2,6	2,10	3,4	3,5	4,6	4,11	5,6	6,12	7,8	7,9	8,10	8,11	9,10	10,12	11,12
-1-	-2-	-3-	-4-	-5-	-6-	-7-	-8-	-9-	-10-	-11-	-12-	-13-	-14-	-15-	-16-	-17-	-18-
+	+	+	+	+	+	+	+	+	+	+	+	+	+	+		+	+
1	1	1	1	1	2	0	1	1	2	1	2	0	1	1	2	1	1
2	0	0	1	1	0	2	2	0	1	1	0	2	2	0	1	1	2
0	2	0	2	0	1	1	1	1	1	1	0	0	0	2	0	2	1
0	0	2	0	2	0	0	0	2	0	2	1	1	1	1	1	1	1

Повторяем процесс склеивания:



1,8	1,14	2,4	2,15	3,9	4,17	5,11	6,10	7,8	9,11	12,16	13,14	14,18	15,17	12
-1-	-2-	-3-	-4-	-5-	-6-	-7-	-8-	-9-	-10-	-11-	-12-	-13-	-14-	-15-
1	1	1	1	1	1	1	2	2	1	2	2	1	1	2
2	2	2	0	2	1	1	2	2	2	2	2	2	2	1
2	0	2	2	0	2	2	1	1	1	0	0	2	2	0
0	2	0	2	2	2	2	0	0	2	1	1	1	1	1

Некоторые столбцы одинаковы: (1,3), (2,5), (6,7), (8,9), (11,12), (13,14). В каждой группе указанных столбцов оставляем по одному экземпляру и продолжаем склеивание:

-1-	-2-	-3-	-4-	-5-	-6-	-7-	-8-	-9-
+	+	+	+		:+		+
1	1	1	1	2	1	2	1	2
2	2	0	1	2	2	2	2	1
2	0	2	2	1	1	0	2	0
0	2	2	2	0	2	1	1	1

1,8	2,6	3,4	5	7	9
-1-	-2-	-3-	-4-	-5-	-6-
1	1	1	2	2	2
2	2	2	2	2	1
2	2	2	1	0	0
2	2	2	0	1	1

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

1	2	2	2
2	2	2	1
2	1	0	0
2	0	1	1

Полученная таблица соответствует стандартной записи НДФ в следующем виде:

.

Таким образом, исходная функция приведена к дизъюнкции простых импликант

, , и .

Для выяснения вопроса о минимальном покрытии строим таблицу импликант:

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

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

Выбрасывание последней импликанты не приводит к неэквивалентности, т.е. не появляются пустые столбцы. Поэтому минимальная дизъюнктивная нормальная форма (НДФ) для исходной функции имеет вид

.

Первая часть рассмотренного алгоритма программируется довольно просто. Нахождение минимального покрытия - нетривиальная задача. В некоторых случаях возможно существование нескольких тупиковых форм.

Контрольное задание 3 lab

Произвести минимизацию СНДФ методом Квайна - Мак-Класки. Построить таблицу истинности для полученной функции и сравнить с исходной.

Варианты задания

1. 0 1 0 1 0 1 1 0 1 0 1

0 0 1 0 1 1 1 0 0 1 1

0 0 0 1 1 1 0 1 1 1 1

0 0 0 0 0 0 1 1 1 1 1

2. 0 1 0 1 0 1 1 1 0 1

0 0 1 1 0 0 1 0 1 1

0 0 0 0 0 0 0 1 1 1

0 0 0 0 1 1 1 1 1 1

3. 0 1 0 0 1 1 1 0 1

0 0 1 0 1 0 0 1 1

0 0 0 1 1 0 1 1 1

0 0 0 0 0 1 1 1 1

4. 0 1 0 1 0 1 1 1 0 0

0 0 1 1 0 1 0 1 0 1

0 0 0 0 1 1 0 0 1 1

0 0 0 0 0 0 1 1 1 1

5. 0 1 0 1 1 1 0 1 0

0 0 1 1 0 0 1 1 1

0 0 0 0 1 0 0 0 1

0 0 0 0 0 1 1 1 1

6. 0 1 1 0 1 0 1 0 1 1 0

0 0 1 1 1 0 0 1 1 0 1

0 0 0 1 1 0 0 0 0 1 1

0 0 0 0 0 1 1 1 1 1 1

7. 1 0 1 0 1 0 1 0 1 1

0 1 0 1 1 0 0 1 1 1

0 0 1 1 1 0 0 0 0 1

0 0 0 0 0 1 1 1 1 1

8. 0 1 1 1 0 1 0 1 0 0 1

0 0 1 0 1 0 1 1 0 1 1

0 0 0 1 1 0 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1 1

9. 1 0 1 0 1 0 0 1 1

0 1 1 0 0 0 0 0 1

0 0 0 1 1 0 1 1 1

0 0 0 0 1 1 1 1 1

10. 0 1 0 0 1 0 1 0 1 1 0 1

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

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

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

11. 1 0 1 0 1 1 1 1 0 1

1 0 0 1 1 0 1 0 1 1

0 1 1 1 1 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1

12. 0 1 0 1 0 0 0

0 1 0 0 1 1 1

0 0 1 1 1 0 1

0 0 0 0 0 1 1

13. 0 1 0 1 0 1 0 1 0 1 0 1

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

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

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

14. 1 1 1 1 1 0 1 0 1

0 1 0 1 0 0 0 1 1

0 0 1 1 0 1 1 1 1

0 0 0 0 1 1 1 1 1

15. 0 0 1 0 1 0 1 0 1 0 1

0 1 1 1 1 0 0 1 0 1 1

0 0 0 1 1 0 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1 1

16. 0 1 1 0 0 1 0 1 0 0

0 0 1 0 0 0 1 1 0 1

0 0 0 1 0 0 0 0 1 1

0 0 0 0 1 1 1 1 1 1

17. 1 1 0 1 0 1 0 1 0 1 1 1

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

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

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

18. 0 0 1 1 1 0 1 1 0

0 1 1 0 1 1 1 0 1

0 0 0 1 1 0 0 1 1

0 0 0 0 0 1 1 1 1

19. 1 0 1 0 0 0 1 1 0 1

0 1 1 0 1 0 0 0 1 1

0 0 0 1 1 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1

20. 1 0 1 0 1 1 1 0 0 1

1 0 0 1 1 0 1 0 1 1

0 1 1 1 1 0 0 1 1 1

0 0 0 0 0 1 1 1 1 1

21. 1 1 1 0 1 0 1 0 1 1 0 1

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

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

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

22. 0 1 1 0 1 0 0 0 1 1

0 0 1 0 0 1 0 1 1 0

0 0 0 1 1 1 0 0 0 1

0 0 0 0 0 0 1 1 1 1

23. 0 1 0 1 0 1 0 1 0 1 0 1

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

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

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

24. 1 0 1 0 1 0 1 0 1 1

0 1 1 0 0 1 0 1 0 1

0 0 0 1 1 1 0 0 1 1

0 0 0 0 0 0 1 1 1 1

1.4 Замкнутые классы. Полнота. Теорема Поста (теория)

Существует пять классов функций, введенных в рассмотрение Постом:

- множество булевых функций, сохраняющих ноль:

.

- класс функций, сохраняющих 1:

.

- класс самодвойственных функций:

.

Двойственная функция

.

Функция самодвойственна, если

.

- класс монотонных функций. Рассмотрим два набора аргументов:

, , , и , , , .

Предположим, что

, , , .

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

.

(Сравнения производить на сравнимых аргументах!)

- класс функций, которые представлены в виде

.

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

Таблица свойств некоторых функций:

0	+	-	-	+	+
1	-	+	-	+	+
	-	-	+	-	+
	+	+	-	+	-

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

Теорема Поста. Для того чтобы система функций была полной, необходимо и достаточно, чтобы она включала в себя хотя бы одну функцию, не принадлежащую классу , хотя бы одну функцию, не принадлежащую классу , хотя бы одну функцию, не принадлежащую классу , хотя бы одну функцию, не принадлежащую классу, хотя бы одну функцию, не принадлежащую классу .

Пример. Рассмотрим 3-ю и 4-ю строки таблицы. Отрицание и конъюнкция - полная система функций,

,

т. е. дизъюнкцией можно не пользоваться.

Контрольное задание

1. Доказать, что отрицание и конъюнкция - полная система.

2. Имеются полные системы, состоящие из одной функции. Доказать, что штрих Шеффера образует полную систему.

3. Доказать, что стрелка Пирса образует полную систему.

4. Выполнить построение СПНФ, использовав варианты, приведенные в подразд. 1.3.

1.5 Моделирование релейно-контактных схем 4 лаб в Visio из первой лабы

Рассмотрим следующую задачу. Жюри состоит из трех членов А, B, C. Председателем жюри является А. После выполнения упражнения большинством голосов выносится вердикт - «зачтено» или «не зачтено». Учитывается, что в случае, когда B и C голосуют «за», а председатель голосует «против», то предложение «за» отвергается. Перед каждым членом жюри имеется кнопка, при нажатии которой его голос интерпретируется как «за». Лампочка загорается, если принято решение «за». Требуется соединить провода, источник питания, ключи (кнопки) и лампочку для автоматизации процесса голосования.

Для решения задачи предварительно составим логическую функцию, считая ее функцией трех логических переменных , , :

Рассмотрим три простейшие схемы (рис. 1.1 - 1.3), в которых стандартное положение ключа (кнопки) - открытое, при замыкании обеспечивается проводимость участка цепи. Для решения поставленной задачи достаточно несколько усложнить схему (рис. 1.4).

Размещено на http://www.allbest.ru/

Рис. 1.1 Схема, реализующая «да» и «нет»

Размещено на http://www.allbest.ru/

Рис. 1.2 Схема, реализующая конъюнкцию

Размещено на http://www.allbest.ru/

Рис. 1.3 Схема, реализующая дизъюнкцию

Размещено на http://www.allbest.ru/

Рис. 1.4 Схема, реализующая функцию

Схема, изображенная на рис. 1.4, и дает решение задачи.

Однако с помощью конъюнкции и дизъюнкции невозможно построить произвольную логическую функцию, поскольку набор функций (,) не образует полного базиса. Его следует дополнить отрицанием. Реализацию отрицания можно, например, получить с помощью так называемого реле, соответствующего каждому ключу. Нажатие кнопки должно замыкать простую цепь, содержащую соленоид. Если стандартное положение ключа открытое, то соленоид своим магнитным полем притягивает подвижную часть ключа до замыкания; если стандартное положение замкнутое, то включение магнитного поля приводит к размыканию, что и реализует функцию «отрицание».

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

Таким образом, логика работы релейно-контактных схем обеспечивается элементами, реализующими операции «И» (конъюнкция), «ИЛИ» (дизъюнкция) и «НЕ» (отрицание). Для построения оптимальной по количеству используемых ключей релейно-контактной схемы следует применить минимизацию. Метод Квайна - Мак-Класки позволяет привести СНДФ к минимальной НДФ. Однако следует иметь в виду, что если отказаться от требования нормальности, то полученную минимальную НДФ в большинстве случаев можно минимизировать далее.

Пример. Дана функция в НДФ:

.

Эту функцию можно записать в виде матрицы

.

Функции соответствует релейно-контактная схема, содержащая два плеча, соединенных параллельно; в одном плече последовательно соединены ключи для реализации A, ?B и C, во втором - , и .

Дальнейшую минимизацию можно осуществить путем вынесения общего множителя:

.

Результат показан на рис. 1.5.

Размещено на http://www.allbest.ru/

Рис. 1.5 Релейно-контактная схема

Котрольное задание

Варианты заданий по данной теме приведены в подразд. 1.3.

Требуется выполнить следующее:

- нарисовать релейно-контактную схему, соответствующую заданной СНДФ;

- методом Квайна - Мак-Класки привести СНДФ к виду минимальной НДФ;

- произвести (если это возможно) дальнейшую минимизацию, используя вынесение общих множителей за скобки;

- нарисовать релейно-контактную схему для полученной логической функции.

1.6 Моделирование сумматоров

С помощью релейно-контактных схем можно построить модель арифметического сложения двоичных чисел. Для этого предварительно воспроизведем операцию сложения двух одноразрядных чисел. Требуется сопоставить с каждым из чисел, принимающих значения 0 и 1, высказывания «участок цепи разомкнут» и «участок цепи замкнут». В табл. 1.2 приведено сложение одноразрядных чисел.

Таблица 1.2 Сложение одноразрядных чисел

		Результат
0	0	00	0	0
0	1	01	1	0
1	0	01	1	0
1	1	10	0	1

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

и .

Первая функция определяет содержимое младшего разряда результата сложения, а вторая - старшего. Соответствующая структурная схема имеет вид, показанный на рис. 1.6.

Размещено на http://www.allbest.ru/

Рис. 1.6 Полусумматор на два входа

По этим таблицам истинности строим СНДФ функций и :

,

.

Используя полученные логические формулы, конструируем соответствующие релейно-контактные схемы. Упрощенно их можно представить в виде схемы (рис. 1.7), которая содержит инверторы (реализующие отрицание), дизъюнкторы (параллельное соединение) и конъюнкторы (последовательное соединение).

Размещено на http://www.allbest.ru/

Рис. 1.7 Структурная схема операции

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

Размещено на http://www.allbest.ru/

Рис. 1.8 Cумматор на три входа

В табл. 1.3 приведено сложение одноразрядных чисел с учетом переноса разряда:

;

.

Таблица 1.3 Сложение одноразрядных чисел с учетом переноса разряда

			Результат
0	0	0	00	0	0
0	0	1	01	1	0
0	1	0	01	1	0
0	1	1	10	0	1
1	0	0	01	1	0
1	0	1	10	0	1
1	1	0	10	0	1
1	1	1	11	1	1

После минимизации функции и можно записать так:



;

.

Одной из важных технических проблем является разбиение процесса функционирования полученного устройства таким образом, чтобы в отдельный момент времени рассматривался один сумматор. Частота, с которой подключаются отдельные блоки, ответственные за один разряд, называется тактовой. Процесс усовершенствования ЭВМ сопровождается увеличением тактовой частоты, что связано с прогрессом в технологии изготовления ключей.

На рис. 1.9 изображена схема из четырех сумматоров (так называемая линейка). Начальный вход равен нулю. На каждом такте вычисляются выходы и . Выход - результат в младшем разряде, выход является входом для следующего сумматора, P0 = 0.

	X3 Y3		X2 Y2		X1 Y1		X0 Y0
P3		P2		P2		P1		P0
S4	S3		S2		S1		S0

Рис. 1.9 Линейка четырех сумматоров с тремя входами

Пример. 1001 + 0101 = ?

Младший (нулевой) разряд:

Первый разряд:

Второй разряд:

Третий разряд:

Четвертый разряд:

Итак, 1001 + 0101 = 01110.

Для моделирования умножения необходимо ввести еще одну операцию - сдвиг влево на разряд, что соответствует умножению на 2, т.е. умножению на 10 в двоичной системе счисления.

Пример. 101101010 * 2 = 101101010 + 101101010 = 1011010100.

Располагая рассмотренными возможностями моделирования, можно реализовать перевод чисел из десятичной системы счисления в двоичную. Предположим, что на клавиатуре набрана цифра 7. С ней сопоставляется двоичное число 111, что должно быть известно заранее. Пусть после этого набрана цифра 4. На экране дисплея возникает число 74. Представим это число в следующем виде: 7*10 + + 4. Числу 10 в двоичной системе соответствует 1010. Умножим 111 на 1010:



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

Двоичным представлением числа 70 является 1000110.

Далее необходимо прибавить число 4, представленное в двоичной системе:

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

Если далее набрать цифру 9, то на экране возникнет число 749. Для перевода его в двоичную систему достаточно представить это число в следующем виде: 749 = 74 * 10 + 9. Произведем умножение числа 74 на 10 в двоичной системе счисления:

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

Для записи числа 749 в двоичной системе к полученному результату достаточно прибавить 1001, что соответствует числу 9 в десятичной системе:

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

Итак, 749 1011101101 (в двоичной системе счисления).

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

Контрольное задание

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

2. ОСНОВНЫЕ ПОЛОЖЕНИЯ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

Логика высказывания является одной из разновидностей формальных теорий.

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

1) множество символов , образующих алфавит;

2) множество слов в алфавите, которые называются формулами;

3) подмножество ; состоит из аксиом;

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

Множества и образуют язык, или сигнатуру. Понятия «истинность» и «ложность» отсутствуют. Существенна лишь выводимость, или доказуемость. Пусть

- формулы теории . Если существует такое правило вывода , что

,

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

по правилу вывода (т.е. не является композицией каких-то иных отношений). Обычно этот факт записывают в виде

.

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

Вывод формулы из формул

- это такая последовательность формул

, что ,

а любая из формул

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

Если формула выводима из формул

в теории , то это обозначается так:

.

Формулы

называются гипотезами вывода. Если формула G непосредственно выводима из аксиом (т.е. без гипотез), то она называется теоремой. Обозначение: .

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

.

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

Формула называется общезначимой (или тавтологией), если она истинна в любой интерпретации.

2.2 Исчисление высказываний

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

1. Множество символов , образующих алфавит:

- и - связки;

- ( , ) - служебные символы;

-

- пропозициональные переменные.

2. Формулы:

- переменные суть формулы;

- если - формулы, то () и () - формулы.

3. Аксиомы:

;

;

.

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

4. Правило:

 - modus ponens.

Другие связки вводятся определениями (а не аксиомами):

.

Если в формулу подставить вместо переменных

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

,

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

называется унификатором. Формула называется совместным частным случаем формул и , если является частным случаем и частным случаем при одном и том же общем унификаторе. Наименьший возможный унификатор называется наиболее общим унификатором.

При конструктивном определении исчисления высказываний помимо приведенного правила modus ponens вводится еще одно, называемое правилом подстановки: если формула является частным случаем формулы , то формула непосредственно выводима из .

Теорема 1. .

Доказательство. В аксиому

:

вместо подставим .

Тем самым выведем формулу

.

По второй аксиоме

: .

Подставим вместо , вместо :

.

Теперь видим, что по правилу modus ponens выводится формула

.

Подключаем

: , заменив на : .

По правилу modus ponens , что и требовалось доказать.

Теорема 2. (правило введения импликации).

Доказательство. - гипотеза.

: - гипотеза .

По правилу modus ponens , что и требовалось доказать.

Теорема 3. Если

, , то ,

и наоборот (дедукция).

Доказательство. Дано: существуют

,

такие, что

, а

- либо аксиомы, либо , либо , либо

, .

Доказательство проводим по индукции. Необходимо доказать, что если существует вывод

, то , ,…

1. Докажем, что

. Дано: , . Доказать: .

Возможны три случая:

а) - аксиома. Применяем первую аксиому:

:.

По правилу МР

, МР , или

(в левой части аксиомы не пишут);

б) . Тогда :.

Предположим, что . Тогда по МР

МР .

Значит,

, .

Но так как

, то

в левой части писать незачем, и

;

в) .

Тогда

, .

Выше было показано, что

.

Принимая правую (выведенную) часть

,

в виде гипотезы и используя

: ,

по правилу МР получаем

.

Это можно записать в виде

. Но , значит, .

2. Пусть



выведены. Выведем

: .

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

.

Используем вторую аксиому :

.

Получаем

.

- это гипотеза индукции, которая считается выведенной. По МР

.

Опять-таки, - гипотеза вывода, и по МР . Результат:

.

При приходим к утверждению теоремы.

Обратная теорема:

.

Доказательство. Примем выведенное утверждение в качестве гипотезы. Если - гипотеза, то по МР . Отсюда

,

что и требовалось доказать.

Следствие 1. Если

, то ,

и обратно.

Следствие 2.

,

(правило транзитивности).

Доказательство.

,

- гипотезы. По правилу МР , - гипотезы. Значит, . Это записываем в виде

, , .

По теореме дедукции

, ,

что и требовалось доказать.

Следствие 3.

,

(правило сечения).

Другие теоремы:

; ; ;

; ;

; , … .

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

1. Использовать методику, приведенную выше. Ее суть - применение аксиом, правил вывода и поиск унификаторов. Каждая выведенная теорема подключается к списку левой части любого вывода. Основное средство - теорема дедукции:

, .

2. С помощью теоремы дедукции привести выводимую в ИВ (исчислении высказываний) формулу к виду теоремы (т.е. от предложенного для вывода перейти к выводу теоремы):

, где .

Далее записать формулу АВ (алгебры высказываний):

.

Можно также использовать рассмотренные в АВ эквивалентности либо составить таблицу истинности (с помощью ЭВМ) и убедиться в тавтологичности этой формулы (т.е. в том, что при любых значениях пропозициональных переменных она принимает значение «истина»). Если это не так, то формула ИВ не является выводимой.

3. В большинстве случаев проще доказывать невыводимость противоположной формулы. Это так называемый метод доказательства от противного:

,,

где - противоречие, что эквивалентно . Докажем выводимость , если выводимо

,.

Для этого, как было сказано выше, приведем вывод формулы

,

к виду теоремы, используя дедукцию:

,.

Теперь запишем соответствующую формулу АВ (в булевой форме) и преобразуем, используя эквивалентности АВ:

.

Это значит, что соответствующая формула ИВ выводима:

.

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

,

т. е. выводимо из , что и требовалось доказать.

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

.

Эту теорему нужно доказать. Используем алгебру высказываний (АВ), считая символ «+» дизъюнкцией, а символ «*» конъюнкцией:

,

что соответствует аналогичной формуле АВ, которую запишем в булевой форме:

.

Придадим поочередно значения 0 и 1:

;

.

Итак, при любых значениях , , данная формула алгебры высказываний имеет значение «истина», что и означает выводимость теоремы

.

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

,

либо в виде правила вывода метода резолюции:

.

Этим правилом вывода, доказанным вполне строго, можно пользоваться наряду с правилом МР.

Знаменатель правила имеет название «резольвента».

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

Пусть - произвольное множество. Предположим, что на нем задана тотальная функция (однозначное отображение) на этом множестве

:

(однозначное отображение), т.е.

.

Эта функция является -парной (или -местной).

Предположим, таких функций несколько:

.

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

Примеры:

Пусть - множество целых чисел. Рассмотрим сигнатуру, состоящую из двух бинарных операций: « + », « * ». Возникает алгебра чисел -

.

Задано произвольное множество и операция « * » (или « + »). Получаемая алгебра называется группой.

Частные случаи:

- = , « * »

- группа целых чисел.

- (, « + ») - группа целых чисел; (2, « + ») - подгруппа группы целых чисел, или группа четных чисел.

Если функции сигнатуры являются произвольными отношениями, то пара (, ) называется моделью.

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

Пример. (2; 4; 10; « + »); 2 + 2 = 4; 2 + 4 = 6 (2; 4; 6; 10; « + ») - все то, что можно получить, и является замыканием (все четные числа).

Элементы сигнатуры называются функторами;

- терм. Отображение некоторого множества термов во множество {И, Л} называется атомом. Он состоит из двух объектов:

,

где - предикат,

- список термов.

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

Указанием на пункт А или Б являются кванторы: «все» - All: ; «существует» - Exists: .

С помощью кванторов исчисление высказываний обогащается новым типом формул:

;

- «И», «Л» в зависимости от .

Переменные, по отношению к которым применим квантор, называются связанными, остальные свободными. В дополнение к этому в исчислении предикатов добавляются новые аксиомы типа

П1 ; П2 ;

MP: :; :.

Формулой исчисления предикатов является любой стандартный набор, содержащий обычные пропозициональные переменные, снабженные кванторами и , а также связками . Кванторы в этой теории применяются лишь к термам. Такая теория называется теорией первого порядка. В теориях высших порядков кванторы применяются также к литералам - именам пропозициональных переменных и предикатов.

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

Основные идеи такого приведения:

.

Пример. Доказать, что число 36 делится на 6. Вместо этого докажем две другие теоремы: 36/2 и 36/3. После доказательства этих теорем следует, что (36/2) и (36/3) (36/6). Значит, исходную формулу желательно представить в виде конъюнкций.

Избавиться от отрицаний перед кванторами:

,

.

.

Пример. Пусть дана плоскость и вектор нормали.

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

.

Алгоритм заключается в выполнении следующих шагов:

Шаг 1. Избавление от импликаций:

.

Шаг 2. «Протаскивание» отрицаний:

.

Шаг 3. Вспомогательная операция - разделение связанных переменных. Основная идея заключается в том, что каждая связанная переменная может встречаться только два раза: первый раз - в обозначении квантора, второй - в обозначении терма:

… … (……) = … … (……).

Например,

- не имеет смысла;

- правильно.

Шаг 4. Приведение к предваренной форме. Основная идея - распространение области действия квантора в наибольшей степени:

,

.

Шаг 5. Сколемизация - избавление от квантора . Вместо квантора появляются произвольные функторы.

Шаг 6. Избавление от квантора (согласно аксиоме ).

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

Шаг 8. Сведение к доказательству предложений - членов конъюнкции. Если каждый из выводов осуществим, то осуществляется вывод всей формулы.

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

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

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

2.4 Приложение исчисления предикатов к аналитической геометрии

С логическими операциями «дизъюнкция» и «конъюнкция» можно сопоставить алгебраические выражения, содержащие операции abs, +, -, /, *.

Операции , - промежуточные:

;

.

Проверка первой формулы:

- пусть , тогда для левой части получим

,

а для правой -

==;

- если , то для левой части получим

,

а для правой -

==.

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

.

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

Пусть

.

Тогда

.

Но если каждая из функций положительна, то наименьшая из них также положительна:

,

Или

,

Где

.

Аналогично вводится функция

.

Для обеспечения дифференцируемости вводится дополнительное усовершенствование, с помощью которого создаются так называемые R-конъюнкция и R-дизъюнкция:

,

.

Параметр должен удовлетворять неравенству

.

С отрицанием сопоставляется предикат следующего вида: если

, то .

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

Рис. 2.1 Область, в которой необходимо найти аналитическое выражение функции

Решение заключается в выполнении нескольких шагов.

1. Запишем уравнения участков границы области:

.

2. Рассмотрим левую часть круга. В этой части области выполняются неравенства

Значение истинности принимает логическая функция следующего вида:

,

Где

.

Соответствующая R-функция имеет вид

.

3. Рассмотрим верхнюю правую часть области. В этой части области выполняются неравенства

.

Значение истинности принимает следующая логическая функция:

,

где .

Последовательно строим соответствующие R-конъюнкции:

,

.

4. Аналогично строим R-функцию

,

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

5. Наконец, R-функция, описывающая область в целом, является R-дизъюнкцией трех найденных R-функций:

.

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

Замечание. Построение R-функции неоднозначно. В рассмотренном примере можно было построить R-функцию, положительную внутри области, границами которой являлись бы прямые 2, 3, 4, а затем найти конъюнкцию отрицания найденной функции и функции

.

Контрольное задание

В пособии [7, стр. 32-35] выбрать свой вариант и выполнить следующее:

Найти уравнения участков границ заданной области, а также соответствующие предикаты, принимающие значение «истина» в заданной области.

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

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

.

3. ВЫЧИСЛИМОСТЬ

3.1. Неформальное определение алгоритма. Примеры

Неформальное определение алгоритма таково: алгоритм - это совокупность определенных правил, позволяющих решить задачу.

Примеры:

при .

, ;

Решение:

; , ;

.

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

Решение. Пусть . Рассмотрим и . В зависимости от их величины, отложим либо

 в , либо в .

Окончание алгоритма: . Искомым отрезком является отрезок .

Всегда ли этот алгоритм конечен? Ответ - нет.

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

Докажем это:

,;

;

.

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

Вариантом алгоритма Евклида является алгоритм нахождения наибольшего общего делителя двух целых чисел:

, ;

;

;

;

; .

Теория алгоритмов в математике рассматривается как формальная теория.

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

Контрольное задание

С помощью алгоритма Евклида решить две задачи: сократить дробь; сократить произведение дробей (табл. 3.1).

Таблица 3.1 Варианты задания

Номер варианта	Сократить дробь	Сократить произведение дробей
1	52725971 / 254437301	77161633/604120273 и 207134329/368859367
2	58552849 / 326769323	15525971/68110201 и 68449807/90174017
3	30071387 / 170007581	176933873/101583107 и 81925829/123110629
4	17850821 / 38830369	104279849/89034301 и 34291541/258238081
5	160313459 / 239773111	4613201/282998921 и 249201371/20641549
6	111246313 / 374840971	17408179/158527297 и 51875869/56038343
7	46187333 / 232771321	11663569/4737323 и 2670827/33630829
8	94062767 / 188748817	327488407/916892029 и 108797989/205615681
9	57609763 / 96401821	193609151/255319723 и 129986167/56572639
10	77718737 / 163343251	149118941/73734071 и 102595453/40453379
11	22735831 / 304181989	107842741/181624727 и 89581363/195091283
12	189893387 / 317475121	34311449/94440121 и 24555577/114690461
13	189851489 / 337434893	22481159/251494459 и 728534899/26604341
14	11394751 / 533138153	3149219/47584891 и 142852999/10422001
15	164866963 / 183307393	30989663/8886803 и 92316083/70098389
16	7755763/22201229	273025681/326332781 и 60182887/142699223
17	5232167/46446797	50707091/475916849 и 96644047/32431037
18	559565177/564351707	100256467/560734051 и 396003901/71545069
19	20938363/461350159	48243703/198544123 и 6291707/60044321
20	19997903/61970549	654536191/37218179 и 20170259/96022133
21	34458659/45917203	167406073/147293749 и 194806331/29949587
22	130976849/208084271	127596197/21055403 и 45447131/23784667
23	87918773/206463031	97471589/173317099 и 51121673/97244647
24	151832357/311301629	342946861/19288891 и 53976619/190839013

3.2 МНР-вычислимые функции

Пусть имеется неограниченное количество регистров

.

В каждом регистре содержится целое число :

			…	…
			…	…

Количество регистров бесконечно,

.

В качестве аксиом принимается набор допустимых операций:

- - обнуление ();

- - прибавление единицы

(),

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

-

- операция переадресации, содержимое регистра заносится в регистр ;

-

- условный переход: если

,

то перейти на команду , если иначе, то выполнить следующую команду.