.
Пусть 
- множество логических функций. Формулой над F называется выражение вида 
, где 
, 
- либо переменная, либо формула. При этом множество F называется базисом, функция f называется главной (внешней) операцией, а - подформулами. Зная таблицу истинности базиса можно составить таблицу истинности функции, которую реализует (задает) данная формула.
Система функций {&,
} образует булев базис, при этом формулы, содержащие только символы конъюнкции, дизъюнкции и отрицания, называются булевыми. Множество логических функций с заданным на нем булевым базисом образуют булеву алгебру.
Основные равносильности в булевой алгебре
(далее вместо записи
будем писать 
или 
)
10. 
, 
;
11. 
, 
;
12. 
, 
;
13. 
, 
;
14. 
;
15. 
, 
, 
, 
, 
; 
;
16. 
, 
;
17. 
;
18. 
.
Формулы, реализовывающие одну и ту же функцию, называются эквивалентными или равносильными. При доказательстве равносильности формул используются основные равносильности булевой алгебры и следующие формулы:
10. 
;
11. 
;
12. 
;
13. 
;
14. 
.
Под упрощением формул понимается получение формул, содержащих меньшее число символов. При упрощении используются равносильности:
15. поглощение: 
, 
;
16. склеивание/расщепление: 
;
17. обобщенное склеивание: 
.
Элементарными конъюнкциями (дизъюнкциями) называются конъюнкции (дизъюнкции) переменных или их отрицаний, в которых каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, каждая конъюнкция которой содержит все переменные или их отрицания. Конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ) определяются аналогично.
Функция 
называется двойственной к функции 
, если 
.
Принцип двойственности: если в формуле F, реализующей функцию f, заменить все знаки функций на знаки двойственных функций, то полученная формула 
будет реализовывать функцию 
, двойственную к f.
Множество логических функций с заданным на нем базисом {&,
} образует алгебру Жегалкина. В алгебре Жегалкина выполнены все равносильности булевой алгебры, касающиеся конъюнкции, а также следующие равносильности:
18. 
;
19. 
;
20. 
;
21. 
.
Логическая функция над базисом Жегалкина единственным образом представима полиномом Жегалкина:
.
Функция называется линейной, если ее полином Жегалкина содержит только линейную часть.
При построении полинома Жегалкина используются равносильности булевой алгебры, алгебры Жегалкина и следующие формулы:
22. 
;
23. 
.
Система логических функций F называется функционально полной, если любая функция реализуема формулой над F.
Теорема. (Поста). Система F логических функций полна тогда и только тогда, когда для каждого из классов Поста в системе F найдется функция, не принадлежащая данному классу.
Классами Поста являются следующие замкнутые классы логических функций:
· класс функций, сохраняющих 0: 
;
· класс функций, сохраняющих 1: 
;
· класс самодвойственных функций: 
;
· класс монотонных функций: 
;
· класс линейных функций: 
, где 
.
Логические функции можно интерпретировать как функции проводимости электрических цепей, содержащих двухпозиционные переключатели (частный случай так называемые релейно –контактные схемы). 1 интерпретируется как состояние переключателя “ ток проходит ”, а 0 – “ ток не проходит ”. x – замыкающий контакт, 
- размыкающий контакт, &- последовательное соединение контактов, 
- параллельное. Две цепи считаются эквивалентными, если через одну из них ток проходит тогда и только тогда, когда он проходит через другую. Из двух схем более простой считается та, которая содержит меньшее число контактов.
23. Записать логической формулой следующие высказывания:
а) если на улице идет дождь, то нужно взять с собой зонт или отменить прогулку;
б) если в 
- прямой и стороны 
и 
равны, то 
.
24. Пусть А= “X любит Y”, В= “Y любит X”. Выразить следующие формулы на обычном языке:
а) 
; б) 
; в) 
; г) 
; д) 
;
е) 
; ж) 
; з) 
; и) 
; к) 
.
25. Установить истинность высказывания: «если Алексей знаком с Борисом и Борис знаком с Викой, то либо Алексей знаком с Викой, либо Алексей не знаком с Викой».
26. На вопрос: «Кто из трех студентов изучал дискретную математику?» Получен верный ответ: «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий». Кто изучал дискретную математику?
27. Определите, кто из четырех студентов сдал экзамен, если известно:
если первый сдал, то и второй сдал;
если второй сдал, то третий сдал или первый не сдал;
если четвертый не сдал, то первый сдал, а третий не сдал;
если четвертый сдал, то и первый сдал.
28. Вычислить значение функции 
на наборах 
и 
.
а) 
; б) 
;
в) 
.
29. Построить таблицы истинности следующих функций:
а) 
;
б) 
;
в) 
;
г) 
;
д) 
;
е) 
.
30. Выяснить какие из следующих формул являются тождественно истинными или тождественно ложными:
а) 
;
б) 
;
в) 
г) 
;
д) 
.
31. Найти СКНФ и СДНФ функций 
(
), заданных таблицей истинности:
32. Найти СДНФ функции с помощью равносильных преобразований:
а) 
; б) 
; в) 
;
г) 
; д) 
; е) 
.
33. Найти СКНФ функции с помощью равносильных преобразований:
а) 
; б) 
; в). 
34. Указать СДНФ, выражающие следующие функции:
а) 
ровно две переменные ложны;
б) большинство переменных равно 1;
в) 
.
35. Найти все существенные переменные функции:
а) 
; б) 
;
в) 
.
36. Найти ДНФ функции 
, двойственной к данной:
а) 
; б) 
.
37. Применить принцип двойственности к следующим равносильностям:
а) 
; б) 
; в) 
.
38. Найти многочлен Жегалкина для функции:
а) 
; б) 
;
в) 
; г) 
.
39. Дана функция проводимости релейно-контактной схемы 
. Построить схему.
а) 
; б) 
.
40. Найти минимальную ДНФ и построить р.-к. схему для функции:
а) 
; б) 
.
41. 
Дана р.-к. схема. Записать функцию проводимости и упростить схему:
а) x б) y z
x y
x z
z 
в) x
x
y x
y
z
z
u
u
42. Из контактов x, y, z составить схему так, чтобы она имела состояние 1, если не менее двух контактов имеют состояние 1.
43. Проверить полноту систем функций:
а) 
; б) 
; в) 
; г) 
; д) 
; е) 
.
44. Проверить принадлежность функций классам Поста:
а) 
; б) 
;
в) 
; г) 
.
Глава VII. Элементы теории автоматов
Конечным детерминированным автоматом (к. д.а.) называется пятерка 
, где 
- входной алфавит, 
- алфавит выхода, 
- алфавит состояний с выделенным начальным состоянием 
, 
- функция переходов, 
- функция выходов. Работа автомата осуществляется в дискретные такты времени 
. Задается автомат с помощью таблицы переходов-выходов (рис.1) или диаграммы Мура (рис.2).
 |
Таблица переходов – выходов. Диаграмма Мура.
Рисунок 1. Рисунок 2.
Реализация к. д.а. осуществляется с помощью канонической таблицы
 |
и канонических уравнений
.
Для этого элементы 
, 
и 
кодируются:
, 
, 
.
Кодовые слова следует выбирать минимально возможной длины, начальное состояние кодируется словом (00…0).
Функциональным элементом называется устройство, вычисляющее элементарную функцию. Элемент, способный удержать единицу информации в течении одного такта называется единичной задержкой или триггером. Зная канонические уравнения к. д.а. можно построить схему логического устройства, которое его реализует (рисунок 3). Для построения схемы используем элемент единичной задержки и элементы, порожденные функциями 
(рисунок 4). Память устройства содержит в себе необходимое количество элементов задержки.
 |
память
Рисунок 3.
x x
x 
y x&y y xvy
Рисунок 4.
Минимизированный к. д.а. – это автомат, реализующий ту же функцию, что исходный, но с минимальным числом состояний. Минимизация автомата проходит следующим образом:
Шаг 1. Разбиваем состояния автомата на классы эквивалентности «по выходам». При этом в одном классе оказываются состояния, которые одинаково реагируют на входные символы на выходе: 
, если 
.
Шаг 2. Полученные на предыдущем шаге классы разбиваем «по переходам». При этом эквивалентными считаем состояния, которые одинаково реагируют на входные символы при переходе, т. е. попадают в один и тот же класс эквивалентности, построенный ранее: 
, если 
. Таким образом происходит «раздробление» уже существующих классов. Возвращаемся на начало шага 2, и повторяем процесс до тех пор, пока количество классов не перестанет увеличиваться.
и задать функции переходов и выходов (построить таблицу и диаграмму Мура), для следующих функций:
а) 
;
б) 
;
в) 
;
г) 
;
д) 
;
е) 
,
здесь 
2. Минимизировать к. д.а., заданный таблицей переходов-выходов.
а) б)
3. По таблицам переходов–выходов автоматов, вычисляющих функции из задачи 1 а) – е), построить канонические таблицы и канонические уравнения к. а. (автомат рекомендуется предварительно минимизировать).
а) 
б) 
здесь
5. Для функций из задачи 1 а)–е) нарисовать схемы устройств, реализующих эти функции, используя элемент единичной задержки и элементы, порожденные функциями .
6. Построить конечный автомат, минимизировать его, построить каноническую таблицу, канонические уравнения. Нарисовать схему устройства, реализующую эту функцию, используя элемент единичной задержки и элементы, порожденные функциями .
а) 
б) 
в) 
г) 
д) 
е) 
здесь
7. По схеме автомата (рисунок 5) построить канонические уравнения, каноническую таблицу, таблицу переходов-выходов и диаграмму Мура.
& 
V & 
&
V 
V
& 
& y
З
З
З
а) б)
Рисунок 5.
ОТВЕТЫ И УКАЗАНИЯ
ГЛАВА I
3а) {b, c}; 3б) {a, b,c, e}; 3в) {a, b}; 3г) {e}; 3д) {b}; 3е) {b, e}; 3ж) {a}; 3з) {b}; 3и) U.
4а) {1,3,5,7,9}; 4б) {6,7,8,9}; 4в) {2,4,5,6,7,8,9,10}; 4г) {4,5}; 4д) {1,3,5};
4е) {5,7,9}; 4ж){1,2,3,6,7,8,9,10}; 4з) {2,5,7,9}; 4и) {1,2,3,4,5,7,9}; 4к) {2,4,7,9};
4л) {6,8,10}. 6а) 
; 6б) 
; 6в) 
. 10а) 
;
10б) 
; 10в) 
; 10г) 
.
ГЛАВА II
1а) 
.
2а) 
;
2б) 
;
2в) 
;
2г)R={(пн.,вт.);(вт.,ср.);(ср.,чтв.);(чтв.,птн.);(птн.,субб.);(субб.,воскр.);(воскр. пн.)};
3а) Dom(R)=Im(R)={1,2,3,4}, 
,
; 3б) 
, 
, Dom(R)=[0,2], Im(R)=[-1;1];
3в) Dom(R)=Im(R)=[0;1], 
;
; 3г) указание: 
.
5г) антирефлексивно, симметрично, не транзитивно; 5д) антирефлексивно, антисимметрично, не транзитивно; 5е) рефлексивно, симметрично, транзитивно;
5ж) рефлексивно, симметрично, транзитивно; 10а) да; 10б) нет; 10в) нет; 10г) да.
11а) нет; 11б) нет; 11в) нет; 11г) да.
ГЛАВА III
4. Второй студент. 5. Экзамен сдали все студенты. 6а) 
, 
;
6б) , 
; 6в) 
, . 7а) 
; 7б) 
; 7в) 
; 7г) 
; 7д) 
;
7е) 
. 8а) т. ложна; 8б) т. истинна; 8в) т. ложна; 8г) т. истинна; 8д) выполнима.
9. 
. 10а) 
;
10б) указание: формула задает константу 1; 10в) 
;
10г) 
; 10д) 
;
10е) указние: 
. 11а) 
; 11б) 
;
11в) 
. 12а) 
;
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
