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

Размещено на 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: , которая с каждой формулой формальной теории сопоставляет некоторое содержательное высказывание относительно объектов множества . Это высказывание может быть истинным, ложным или не иметь значения истинности. Если соответствующее высказывание является истинным, то формула выполняется в данной интерпретации. Интерпретация называется моделью множества формул, если ...