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

Шаг 3. Используя тождества, исключить из ППФ операции « », « », « ».

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

Шаг 5. Конец.

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

Пример 10

Определить кто из приятелей солгал и кто не солгал, если они дали такие показания.

– Мы с Борисом не лжем, а лжет Виктор, – сказал Андрей.

– Не знаю, кто лжет, но мы с Андреем не лжем, – сказал Борис.

– Если Андрей лжет, то и Борис лжет, – сказал Виктор.

Решение. Введем обозначения для атомарных высказываний: А – «Андрей не лжет»; Б – «Борис не лжет»; В – «Виктор не лжет». Тогда формула будет означать, что Андрей лжет. Аналогично определится смысл и у формул и . Показания Андрея определятся следующей элементарной конъюнкцией . Данная формула будет иметь то же значение, что и формула , откуда следует ППФ . По показаниям Бориса и Виктора аналогичным образом получаются формулы и соответственно (проверьте, что это так). Тогда условие нашей задачи (вся совокупность показаний) определится конъюнкцией последних трех формул, т.е. получается ППФ следующего вида

( )( )( ) .

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

Теперь избавимся от операций « » и « » (шаг 3). Получим

( )( )( ).

Полученную булеву формулу упростим с помощью тождественных преобразований (шаг 4). Будем иметь

( )( )( ).

Откуда раскрывая скобки получим

( )( )(

(

(

.

Получившаяся в результате наших вычислений элементарная конъюнкция означает, что солгали Андрей и Борис, а Виктор сказал правду.

Пример 11

Задача. Девчонки из 6 «В» Кукушкина, Мушкина и Лягушкина получили на 8Марта в подарок кактус, шка­тулку и шоколадку.

1. Если Лягушкина полу­чила кактус, то Мушкина ­– шоколадку.

2. Если Лягушкина получила шоколадку, то Мушкина – кактус.

3. Если Мушкиной подарили не шкатулку, то Кукушкиной – не шоколадку.

4. Если Кукушкиной достался кактус, то Лягушкиной – шоко­ладка.

5. Если Кукушкиной досталась шкатулка, то Лягушкиной – кактус.

Мы тут совсем за­путались, но ты-то, наверное, сможешь решить, кому что все-таки подарили!

---

Решение.

Ведем обозначения. Обозначим прописными буквами девочек:

М­­ – Мушкина,

К – Кукушкина,

Л – Лягушкина.

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

к – кактус,

ш – шоколадка,

т – шкатулка.

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

Лт – Лягушкина получила шкатулку,

Мк – Мушкина получила кактус,

Кш – Кукушкина получила шоколадку.

Согласно условию задачи каждая девочка получила только один подарок. Например, если Лягушкина получила шоколадку (Лш), то Мушкина и Кукушкина шоколадку получить не могут, в этом случае возможны две альтернативы: Мушкина получила кактус (Мк), Кукушкина – шоколадку (Кт), или Кукушкина получила кактус (Кк), а Мушкина шоколадку (Мш). Выражения, содержащие данную информацию можно записать в виде следующих конъюнкций:

Лш Мк Кт

Лш Кк Мт

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

Лш Мк Кт

Лш Мт Кк

Лк Мш Кт

Лк Мт Кш (4)

Лт Мш Кк

Лт Мк Кш.

Кроме того, будут ложны все выражения типа

Лш Лк, Мк Мш,

ЛшМш, ЛкКк…,

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

Запишем выражения, соответствующие условиям задачи:

1. ЛкМш,

2. Лш Мк,

3. ,

4. КкЛш.

5. КтЛк.

Поскольку все эти условия и условие единственности подарка (4) должны выполняться одновременно получим выражение:

(Лш Мк Кт  Лш Мт Кк  Лк Мш КтЛк Мт Кш Лт Мш Кк Лт Мк Кш)

( ЛкМш)(Лш Мк)( )(КкЛш) (КтЛк).

Избавляясь от импликаций получим:

(Лш Мк Кт  Лш Мт Кк  Лк Мш КтЛк Мт Кш Лт Мш Кк Лт Мк Кш)

( Мш)(Мк)( Мт )(Лш) (Лк).

Отсюда, выполняя элементарные преобразования с учетом получим:

(Лш Мк Кт  Лш Мт Кк  Лк Мш КтЛк Мт Кш Лт Мш Кк Лт Мк Кш)  Лк Мш КтЛт Мш Кк)(Мк)(МтМтЛш Лш) (Лк).

С учетом того, что Кт (Кукушкина не получила ни шоколадку, ни кактус тождественно тому, что она получила шкатулку) и Лш=Лш (если Лягушкина получила шоколадку, очевидно, что Кукушкина ее не может получить) получим:

(Лш Мк Кт  Лш Мт Кк  Лк Мш КтЛк Мт Кш Лт Мш Кк Лт Мк Кш)  Лк Мш Кт  Лт Мш Кк)(Мк)(МтМтЛшКтЛш) (Лк) =

=(Лш Мк Кт  Лш Мт Кк  Лт Мш Кк  Лт Мк Кш  Лк Мш Кт) (Мк) (МтМтЛшКтЛш) (Лк)=

=( Лт Мш Кк Лт Мк Кш  Лк Мш Кт Лш Мк Кт)( Мт Лш Мт КтЛш)

(Лк) = (Лк Мш КтЛш Мк Кт) (Лк) = Лк Мш Кт.

---

То есть, Лягушкина получила кактус, Мушкина – шоколадку, а Кукушкина – шкатулку.

Из последнего выражения видно, что если использовать только первые четыре условия то получим два ответа, не противоречащие в данном случае условию задачи: Лк Мш Кт и Лш Мк Кт, т.е. еще добавляется ответ: Лягушкина получила шоколадку, Мушкина – кактус, а Кукушкина – шкатулку. В общем случае можно получить множество решений, формально выводимых из условия, однако конечно, гораздо интереснее смотрятся те задачи, в которых мы путем применения аппарата алгебры высказываний получаем единственный правильный ответ.

Варианты заданий к практическим занятиям

Ниже приведены варианты заданий ПФ, зависящих от 3, 4 и 5 аргументов, необходимые для выполнения практических занятий 1 – 5. В табл. 9 занесены числовые представления полностью определенных ПФ. В табл.10 представлены неполностью определенные ПФ (числа, записанные в скобках, задают номера наборов аргументов, где ПФ не определена).

Таблица 9

№ п/п	n=5	n=4	n=3
1	2	3	4
1	0,1,2,3,4,6,10,15,19,25,31	0,2,3,4,5,6,7,8,9,10, 14	0,1,2,3,4
2	4,7,9,10,12,13,14,15,19,20,22,23,26, 31	0,1,2,3,6,7,9,10,11,12,13	0,4,5,6,7
3	3,4,5,6,7,11,12,13,14,15,16,19,20,21,22,25, 27,28,30	6,9,10,13,14,15	0,2,4,5,6
4	0,2,3,4,5,6,8,10,18,19,21,22,23,24,25	0,4,6,7,8,9,10,11,14	0,3,4,5,6
5	1,3,5,10,13,14,15,19,22,23,24,25,26,29	0,2,5,6,13,15	0,1,5,6,7
6	2,8,9,10,11,12,15,16,17,18,19,20,23,25,26,31	0,1,2,6,7,8,9	0,5,6,7
7	0,1,3,4,6,7,9,10,11,12,13,14,15,16,17,20,21,22,23,24,26,28,29,30	0,3,4,5,6,7,8,13,14	0,2,6
8	1,3,4,5,6,7,8,11,13,14,15,17,18,20,21,22,23, 24,25,26,27,28,29,30,31	0,1,3,7,8,9,13	3,4,5,6,7
9	2,3,4,5,6,7,11,14,15,16,17,19,22,24,26,27,28,31	1,2,9,10,13,14,15	2,3,4,5
10	1,3,4,5,8,11,12,15,18,19,20,21,25	0,6,7,8,10,11,12,13, 14,15	3,6,7
11	0,1,3,5,9,11,12,13,14,15,16,17,22,23,30	0,1,2,3,4,6,10,12	0,2,3,4,6
12	1,2,3,4,5,6,7,9,10,12,13,15,17,19,21,22,24,25,29, 30	0,1,2,3,4,5,6,8,9,14, 15	0,4,5,7
13	1,4,5,7,9,15,20,21,22,23,30,31	4,5,7,9,10,11,12,13	0,2,4,5,6
14	0,1,8,9,12,14,16,17,19,20,21,26,27,29	2,3,6,7,9,11,12,13,14	0,1,3,4
Окончание табл. 9
1	2	3	4
15	1,4,5,6,7,8,12,14,16,20,21,22,23	0,1,5,7,8,9,10,14,15	0,2,5,7
16	3,4,5,6,7,9,11,13,14,18,19,20,21,23,24,25,26,27,30,31	0,1,2,3,4,8,9,10,11,13,15	0,1,5
17	0,1,6,7,16,17,20,22,24,25,29,30	2,3,6,7,8,14,15	1,3,4,6
18	0,4,5,9,13,17,18,19,20,21,22,25,26,29,30	0,1,4,6,8,9,10,11, 12,15	0,1,4,5,7
19	1,3,5,8,10,11,12,15,17,19,21,22,23,24,26,28, 31	0,1,2,3,4,6,7,9,12, 14,15	1,3,5
20	2,5,6,8,9,10,13,15,18,19,20,21,22,23,24,26, 27,28,29,31	1,3,5,6,7,10,13,14	0,3,5,6,7
21	2,4,5,9,11,12,13,15,17,18,19,20,21,22,23,24,25,27,29,31	2,3,5,7,8,9,10,11, 13,15	0,2,3,4,7
22	0,1,4,5,8,9,11,13,18,19,20,21,24,27,29	0,1,2,7,8,9,10,11, 12,13,14,15	0,1,2,6,7
23	1,6,8,9,10,12,14,17,18,19,22,24,25,26,28,30, 31	1,5,6,8,9,10,11,14, 15	0,1,2,4,6,7
24	1,3,4,5,6,7,8,9,17,19,22,26,28,29	0,1,4,5,6,7,12,13,14	0,4,6,7
25	0,1,2,3,4,6,7,9,11,13,14,15,16,20,24,27,29,30,31	1,3,7,9,10,11,15	0,1,6
26	2,7,9,10,12,15,18,19,20,24,26,29,30	1,4,7,8,9,10,12, 14,15	2,6,7
27	1,2,3,5,8,10,11,13,14,16,18,19,21,27,28,29	1,5,8,9,13,14,15	0,2,5,6,7
28	0,1,2,3,5,6,11,12,13,16,17,20,21,23,24,27,28, 29,30,31	1,2,3,7,8,9,10,15	0,1,2,4,5,7
29	5,13,15,16,17,19,21,22,23,24,25,28,29,30	1,4,6,8,9,10,11,12, 14	2,3,4,6
30	2,3,6,7,8,10,15,18,19,20,22,24,26,28,30	1,5,7,10,12,13,14,15	2,5,6,7

---

Таблица 10

№ п/п	n=5	n=4	n=3
1	2	3	4
1	5,7,8,9,10,13,15,18,25,26,27,29,30,31 (11,17,19,21,22,24)	4,11,12,14,15 (5,6,7,10,13)	2,4 (6,7)
2	0,4,5,8,9,10,14,16,21,22,23,25,26,30 (1,2, 6,7,11,13,17,24,29)	0,2,5,7,13,14 (1,4, 6,8,10,15)	1,2,3,6 (5)
3	4,5,9,12,17,19,23,25 (1,3,7,11,18,20,21, 22,24,26,27,28,29,30,31)	1,3,7,8,12,15 (2,9,11, 14)	0,4,7 (1,2,5,6)
4	0,2,5,7,12,18,20,21,22,23,27,29 (1,3,4,6,9, 14,16,17,19,24)	3,12,13 (6,8,9,11, 15)	1,2,4,6 (3)
5	0,6,8,9,14,16,18,20,21,26,28,30 (2,3,5,10,13, 17)	3,8,11,14 (1,2,4,9, 10,13,15)	0,1,3,5, 6,7 (2)
Продолжение табл. 10
1	2	3	4
6	0,1,2,3,4,5,6,12,14,20,26,27,28,29 (7,8,13,16,18,19,21,22,24,30)	1,9,11,12,14 (3,4,7,8,10,15)	1,5,7 (4)
7	0,1,6,8,9,23,24,31 (2,3,5,7,10,11,13,15, 20,22,27,29,30)	0,4,8,10,11,13 (3,5,9,12,14,15)	3 (4,5,6,7)
8	4,9,19,20,23,26,27,28,29,30 (2,3,6,8,10,11,12,13,24,25,31)	0,2,3,6,8,14 (1,4,7,12)	0,4,6 (2,3,5,7)
9	0,4,6,14,16,17,21,29 (1,3,5,7,9,11,13,15,18, 19,20,24,25,26,27,28,31)	0,7,13 (4,5,9,11,14,15)	3,4 (0,1, 2,5,6)
10	4,7,8,10,11,13,15,20,27 (5,6,9,14,16,21, 22,23,29)	8,13,15 (0,6,7,10, 11,12,14)	1,3,4,5 (0,6,7)
11	0,8,12,14,15,17,26,30 (1,7,9,10,16,18,20,22, 24,28,31)	4,5,8,11 (1,3,6,7,9,13)	0,3,4,6 (7,2)
12	4,5,12,17,19,21,23 (0,2,3,6,13,16,20,22, 24,25,30)	5,6,7,8,12 (0,1,3,4,10,11,15)	0,1,5,7 (2,4,6)
13	0,1,5,12,13,15,20,21,24,28,29 (6,8,11, 14,16,17,25,26,27)	3,7,8,11,15 (2,9, 13,14)	6, 0 (2,5,7)
14	0,2,3,11,16,26,27,30 (7,9,19,21,24,27,28)	0,1,2,5,6,8 (9,10,12,14)	1,4,5 (2,6,7)
15	2,4,8,14,19,22,27,28,30 (1,3,6,7,10,11,12,15, 18,20,23,24,26,29)	1,4,5,7,12,13 (0,2, 6,9,11)	0,2,6 (1,3,5,7)
16	2,6,10,12,13,14,22,23,24,26 (0,1,7,18,25, 27,28,29)	7,8,11,13,15 (0,1,2,3,5)	1,4,5,7 (0)
17	2,7,9,22,23,26,31 (4,5,6,8,10,12,13,14,15, 19,28,29,30)	0,8,10,11,12, (1,9,13,14)	0,3 (2,4)
18	0,2,4,6,8,20,23,28,30 (3,5,7,9,11,16,19, 24,26,27,29,31)	0,2,4,6,9,11,12 (5,8,13,14)	1,6 (2,4)
19	2,5,6,7,15,18,19,22,23,24,25,26,27,28,31 (0,3,8,9,10,13,14,29)	1,2,5,8,11 (3,4,7,9,10,12,13)	1,2,3 (5,6,7)
20	1,4,6,12,14,15,16,17,21,23,26 (0,2,3,8,10, 18,19,28,29,31)	2,3,7,10,13,14,15 (0,5,6,9)	3,6 (0,2,5)
21	0,1,3,17,18,23,25,28,30 (2,4,6,7,8,12,16,19, 21,22,27,31)	2,7,8,10,13,15 (0,3,4,5)	1,2,3,6,7 (0,5)
22	1,8,11,24,25,31(3,6,7,9,10,13,15,16,19,23,26,28,30)	0,6,12,14 (1,2,4,5, 8)	0,1,4,5,6 (2)
23	3,4,5,7,9,18,26 (0,1,11,15,19,23,24,25, 27,28,30,31)	0,4,5,8,12 (1,3,7, 10,14)	0,3,4,5,7 (2,6)
24	0,2,5,9,14,16,17,19,25,29,30,31 (1,3,4,7,10, 13,15,18,26)	1,4,6,12,14,15 (2,5,7,9)	0,4,7 (1,2,3,5)
25	0,2,3,8,11,12,13,18,20,26 (5,13,16,19,21,24,25, 27,28)	0,3,9,10,15 (1,2,8, 11,12,13,14)	2,6 (0,1,3,7)
26	0,2,3,4,5,8,14,16,17,18,19 (1,7,10,12,17,21, 24)	2,5,7,12,13,14 (1,3,4,6,8,9,10)	0,2,4,5,7 (3,6)
Окончание табл. 10
27	1,3,9,10,17,23,25,26,29 (0,5,6,11,15,16, 20,21,27,31)	7,8,10,11,12,13 (0,1,2,3,9)	0,1,2 (3,4,5,6)
28	2,3,4,5,8,12,13, 16,17,28 (0,14,21,23,29,30)	0,2,3,5,11,13,15 (7,9,12)	1,4,5,6 (0,2,7)
29	1,11,22,24,25,26,27,29 (4,8,12,15,17,18,30,31)	0,1,3,6,9,10,11,12, 13 (4,5,7,14,15)	1,3,5,6 (0,7)
30	6,7,10,11,12,14,15,19,22,27 (0,2,3,4,8,9,18,25, 28,31)	0,2,4,12,14 (8,10, 11,13,15)	1,2,4,6 (0,1,3,5)

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

1. Савельев А.Я. Основы информатики. – М.: Изд-во МГТУ им. Баумана, 2001. – 327 с.

2. Савельев А. Я. Арифметические и логические основы цифровых автоматов. –М.: Высш. школа, 1980. – 255 с.

3. Майоров С. А., Новиков Г. И. Принципы организации цифровых машин. – Л.: Машиностроение, 1974. – 432 с.

4. Проектирование цифровых вычислительных машин / Под ред. С. А. Майорова. М.: Высш. школа, 1972. – 344 с.

5. В.И. Потапов и др. Основы компьютерной арифметики и логики: Учеб. пособие / В.И. Потапов, О.П. Шафеева, И.В. Червенчук. – Омск: Изд-во ОмГТУ, 2004. – 172 с.

6. Нефедов А.В. Интегральные микросхемы и их зарубежные аналоги: Справочник: в 8 т. – М.:ИП РадиоСофт, 2001.

7. Интегральные микросхемы: Справочник / Под ред. Б. В. Тарабрина. – М.: Энергоатомиздат, 1985.– 528 с.

8. Методические указания к практическим занятиям по курсу «Прикладная теория цифровых автоматов» / Сост. И.А. Пальянов, О.П. Шафеева. – Омск: Изд-во ОмПИ, 1987. – 36 с.

---

СОДЕРЖАНИЕ

1. Практическое занятие 1. Минимизация переключательных функций

с помощью карт Карно 3

2. Практическое занятие 2. Минимизация переключательных функций

методом Квайна – Мак-Класки 7

3. Практическое занятие 3. Синтез комбинационных схем в базисе

«И, ИЛИ, НЕ» 12

4. Практическое занятие 4. Синтез комбинационных схем

на логических элементах И-НЕ и ИЛИ-НЕ 15

5. Практическое занятие 5. Синтез комбинационных схем в смешанных

базисах 18

6. Практическое занятие 6. Синтез комбинационных схем с исполь-

зованием дешифраторов и мультиплексоров 19

7. Практическое занятие 7. Алгебра высказываний 25

8. Варианты заданий к практическим занятиям 29

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

---

Смотрите также файлы

• Работа с БД.pdf

• программм 2 Кейс-задание 1.pdf

• База Данных интернет-магазина курсовая.pdf

• Курсовая Разработка организационноо-правового обеспечения.docx

• ИС детского сада.docx