МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Сборник индивидуальных заданий
Часть I
Логика высказываний
ВЛАДИКАВКАЗ 2014
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
СЕВЕРО-КАВКАЗСКИЙ ГОРНО-МЕТАЛЛУРГИЧЕСКИЙ ИНСТИТУТ
(ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ)
Кафедра математики
МАТЕМАТИЧЕСКАЯ логика
И ТЕОРИЯ АЛГОРИТМОВ
Сборник индивидуальных заданий
Часть I
Логика высказываний
для студентов направления подготовки
230100.62 - "Информатика и вычислительная техника"
Составитель:
Допущено
редакционно-издательским советом
Северо-Кавказского горно-металлургического института
(государственного технологического университета)
ВЛАДИКАВКАЗ 2014
УДК 519.6(07)
ББК 22.19
К 85
Рецензент:
канд. физ.-мат. наук, доц. СКГМИ (ГТУ) ГРИГОРОВИЧ Г. А.
К 85 Математическая логика и теория алгоритмов: Сборник индивидуальных заданий. Часть I: Логика высказываний / Сост. ; Северо-Кавказский горно-металлургический институт (государственный технологический университет). – Владикавказ: Северо-Кавказский горно-металлургический институт (государственный технологический университет). Изд-во “Терек”, 2014. – 28 с.
Практикум предназначен для приобретения навыков в применении различных методов построения доказательств в логике высказываний. Рекомендовано для студентов направления подготовки 230100.62 - “Информатика и вычислительная техника”.
УДК 519.6(07)
ББК 22.19
Редактор:
Компьютерная верстка:
Ó Составление. Северо-Кавказский горно-металлургический институт (государственный технологический университет), 2014
Ó , составление 2014
Подписано в печать. Формат 60 х 84 1/16. Бумага офсетная. Гарнитура “Таймс”. Печать на ризографе. Усл. п.л. . Тираж 30 экз. Заказ №_____
Северо-Кавказский горно-металлургический институт (государственный технологический университет). Изд-во “Терек”.
Отпечатано в отделе оперативной полиграфии СК ГТУ (ГТУ).
4.
Сборник индивидуальных заданий состоит из 30 вариантов типовых заданий, содержание и трудность которых соответствуют государственному стандарту.
Каждый вариант содержит пять заданий. Задания I – III посвящены изучению таких понятий как функции алгебры логики, принцип двойственности, совершенные дизъюнктивные и конъюнктивные нормальные формы, а также способов реализации булевых функций равносильными формулами. Задание IV относится к исследованию булевых функций на полноту. Задания V и VI содержат задачи, относящиеся к минимизации булевых функций.
Студент выполняет задания своего варианта в отдельной тетради или на листах формата А4 и сдаёт преподавателю, ведущему практические занятия, до проведения текущего контроля по теме: “Логика высказываний”. Выбор варианта соответствует порядковому номеру фамилии студента в журнале преподавателя.
Сокращения, используемые в работе
СДНФ – совершенная дизъюнктивная нормальная форма,
СКНФ – совершенная конъюнктивная нормальная форма,
РКС – релейно-контактная схема,
ДНФ – дизъюнктивная нормальная форма.
– функция, двойственная функции f,
– функция f(х1, х2, …, хп),
– сокращённая дизъюнктивная нормальная форма,
– минимальная дизъюнктивная нормальная форма.
УСЛОВИЯ ИНДИВИДУАЛЬНЫХ ЗАДАНИЙ
I. С помощью равносильных преобразований для данных функций 1) и 2) построить СДНФ и СКНФ:
II. Упростить формулу 
и составить РКС.
III. Построить формулу , реализующую функцию, двойственную функции 
, используя принцип двойственности. Проверить, равносильна ли данная формула 
полученной формуле .
IV. Исследовать на полноту систему булевых функций В, используя теорему Поста.
V. Для данной ДНФ D построить и найти по методу Блейка.
VI. Найти для функции 
с вектором значений 
с помощью карт Карно.
Вариант № 1
I. 1) 
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 2
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 3
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 4
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 5
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 6
I. 1) 
;
2) 
.
II. 
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 7
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
Вариант № 8
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 9
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 10
I. 1) 
2) 
II. 
.
III. 
; 
.
IV. В =
.
V. D 
VI. 
.
Вариант № 11
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 12
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 13
I. 1) 
2) 
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. .
Вариант № 14
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 15
I. 1) 
;
2) 
.
II. 
и составить РКС.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
Вариант № 16
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 17
I. 1) 
;
2) 
.
II. 
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 18
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 19
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 20
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
VI. 
.
Вариант № 21
I. 1) 
;
2) 
.
II. 
.
III. 
, 
.
IV. В =
.
V. D 
VI. 
.
Вариант № 22
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
Вариант № 23
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
VI. 
.
Вариант № 24
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 25
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI.
Вариант № 26
I. 1) 
;
2) 
.
II. 
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 27
I. 1) 
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 28
I. 1) 
;
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 29
I. 1) 
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
Вариант № 30
I. 1) 
2) 
.
II. 
.
III. 
; 
.
IV. В =
.
V. D 
.
VI. 
.
ПРИМЕРЫ ВЫПОЛНЕНИЯ ТИПОВЫХ ЗАДАНИЙ
Для выполнения задания I – III необходимо воспользоваться следующими равносильными формулами и теоремами:
Равносильности, выражающие одни логические операции
через другие
Равносильности, выражающие основные законы алгебры логики
Знак конъюнкции & можно опускать.
Теорема. Всякая булева функция имеет единственную совершенную дизъюнктивную (конъюнктивную) форму, т. е. ДНФ (КНФ), удовлетворяющую свойствам совершенства:
1) каждая элементарная конъюнкция (дизъюнкт) формулы содержит все пропозициональные переменные, входящие в функцию f(x1, x2,..., xn);
2) все элементарные конъюнкции (дизъюнкты) формулы различны;
3) ни одна элементарная конъюнкция (дизъюнкт) формулы не содержит одновременно переменную и ее отрицание и не содержит одну и ту же переменную дважды.
Для получения СДНФ (СКНФ) необходимо сначала исходную функцию с помощью равносильных формул упростить и получить одну из ДНФ (КНФ).
Для выполнения свойств совершенства воспользуемся следующими правилами:
1) если в полученной ДНФ (КНФ) элементарная конъюнкция (дизъюнкт) В не содержит переменную хi, то заменим её (его) на 
Ú
;
2) если в ДНФ (КНФ) входят две одинаковые конъюнкции (два одинаковых дизъюнкта) В, то одну отбросим;
3) если некоторая конъюнкция (дизъюнкт) В содержит переменную хi дважды, то одну переменную хi отбросим;
4) если некоторая конъюнкция (дизъюнкт) В содержит переменную хi и ее отрицание, то конъюнкцию (дизъюнкт) В отбросим.
I. С помощью равносильных преобразований для булевой функции 
построить СДНФ и СКНФ.
Построим СДНФ.
II. Упростить формулу 
и составить РКС.
С помощью равносильных формул выразим данную функцию через конъюнкцию, дизъюнкцию и отрицание переменной. Далее, учитывая, что конъюнкцию двух высказываний р и q можно представить двухполюсной схемой с последовательным соединением двух переключателей (рис. 1), а дизъюнкцию – с параллельным соединением (рис. 2), построим РКС.
Рис. 1. Рис. 2.
|
|
| ||
| |||
 |
III. Построить формулу , реализующую функцию, двойственную функции 
, используя принцип двойственности. Проверить, равносильна ли формула 
полученной формуле .
Функция f*(х1 х2,..., хп), определённая следующим образом
f*(х1 х2,..., хп) 
,
называется двойственной функцией к функции f(х1 х2,..., хп).
Принцип двойственности. Если функция f реализуется формулой С = Ф
, то двойственная ей функция реализуется формулой С*, имеющей такое же строение, что и формула С, т. е. С* = Ф*
.
Для функции по принципу двойственности найдём :
Таким образом, 
Используя равносильные формулы, упростим формулу g:
Обе функции выполнимые, но ¹ g.
Для выполнения задания IV необходимо воспользоваться следующим теоретическим материалом.
Специальные классы булевых функций
Опр. 1. Булева функция f называется функцией, сохраняющей константу 0, если f(0, 0, …, 0) = 0. Множество всех булевых функций, сохраняющих константу 0, образует класс K0.
Опр. 2. Булева функция f называется функцией, сохраняющей константу 1, если f(1, 1, …, 1) = 1. Множество всех булевых функций, сохраняющих константу 1, образует класс K1.
Опр. 3. Булева функция называется самодвойственной, если она совпадает с двойственной себе функцией, т. е. имеет место равенство f = f*. Класс самодвойственных функций обозначается – S.
Опр. 4. Булева функция f называется линейной, если она может быть записана в следующем виде (называемом полиномом Жегалкина)
f(х1, х2,..., хп) = 
Å с1х1 Å с2х2 Å …Å спхп ,
где 
.
Множество всех линейных булевых функций обозначается – L.
Набор значений переменных (s1, s2,..., sп) не меньше набора (s¢1, s¢2,..., s¢п), если sj ³ s¢j для всех j = 1, 2,..., n. В этом случае записывается (s1, s2,..., sп) ³ (s¢1, s¢2,..., s¢п). В противном случае наборы называются несравнимыми.
Опр. 5. Булева функция называется монотонной, если для любых двух наборов, таких, что (s1, s2,..., sп) ³ (s¢1, s¢2,..., s¢п), имеет место неравенство f(s1, s2,..., sп) ³ f(s¢1, s¢2,..., s¢п). Множество всех монотонных булевых функций обозначается – М.
Теорема (Поста). Для того чтобы система булевых функций В ={f1, f2, …, fn} была полной, необходимо и достаточно, чтобы для каждого из классов K0, K1, S, L, М в системе В нашлась функция fi, ему не принадлежащая.
Алгоритм исследования полноты системы булевых функций
1. Построить таблицу, в которой пять столбцов, соответствующих классам K0, K1, S, L, М, и число строк, равное числу функций fi.
2. Проверить принадлежность функции f1 к классу K0 и поставить на пересечении строки f1 и столбца K0 «+», если f1 Î K0, и «-», если f1 Ï K0.
3. Если поставлен знак «+», то продолжить исследование по вертикали, в противном случае – по горизонтали.
4. Вывод: если в каждом столбце есть хотя бы один минус, то теорема Поста выполняется, т. е. система функций полная.
IV. Исследовать на полноту систему булевых функций В =
, используя теорему Поста.
Проверим принадлежность функций 
специальным классам булевых функций. Составим таблицу истинности для этих функций.
х | у |
| ху |
|
0 | 0 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 1 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
Из таблицы видно, что:
; 
;
.
Для того чтобы данные функции принадлежали классу линейных функций необходимо и достаточно представление их в виде
f(х, у) = с0 Å с1х Å с2у.
, где = 0, с1 = с2 = 1.
Представим ху и 
в виде полинома Жегалкина:
х | у | ху |
|
0 | 0 | 0 | 0 = |
0 | 1 | 0 | 0 = 0 Å 0 Å с2 Å 0 Þ |
1 | 0 | 0 | 0 = 0 Å с1 Å 0 Å 0 Þ |
1 | 1 | 1 | 1 = 0 Å 0 Å 0 Å с3 Þ |
= 0
= 0
= 1Таким образом, ху = 0 Å 0х Å 0у Å 1ху , т. е. 
х |
|
|
0 | 1 | 1 = |
1 | 0 | 0 = 1 Å с1 Þ с1 = 1 |
Таким образом, = 1 Å 1х, т. е. 
Используя определение двойственных функций, т. е. f*(х1, х2,..., хп) , найдём 
:
º 
;
º 
;
.
Составим таблицу Поста данной системы булевых функций:
| K0 | K1 | L | М | S |
| + | - | + | - | - |
| + | + | - | + | - |
| - | - | + | - | + |
Функция Классы
Из таблицы видно, что хотя бы одна из функций системы не принадлежит классу K0, K1, S, L, М. Это означает, что рассматриваемая система функций полна.
Для выполнения задания V необходимо воспользоваться методом Блейка.
Метод Блейка состоит в применении правил обобщенного склеивания 
и обобщенного поглощения 
к произвольной ДНФ.
Теорема 1 (Блейк). В результате применения конечного числа операций обобщенного склеивания и поглощения к произвольной ДНФ булевой функции f(x1,..., xп) будут получены все ее простые импликанты, то есть сокращенная ДНФ.
Теорема 2. Если сокращенная ДНФ булевой функции f(x1, х2,.., xп) не содержит отрицаний переменных, то она является единственной минимальной формой этой функции.
После нахождения сокращенной ДНФ булевой функции f(x1, х2,.., xп), содержащей отрицания переменных, строят импликантную матрицу, представляющую собой таблицу, в которой каждой строке соответствует простая импликанта, а каждому столбцу - набор значений переменных, на которых булева функция равна единице. Если простая импликанта покрывает некоторую единицу функции, то в соответствующем столбце ставится пометка - крестик ´.
Для получения минимальной (тупиковой) ДНФ, выбирают такую совокупность простых импликант, которая покрывает все единицы булевой функции. Такая совокупность будет иметь хотя бы один крестик в каждом столбце импликантной матрицы.
V. Для данной ДНФ D 
построить сокращённую ДНФ по методу Блейка и найти минимальную ДНФ.
Первый этап
На первом этапе последовательно для каждой элементарной конъюнкции применим правило обобщенного склеивания .
1) 
,
,
2) вторую конъюнкцию нельзя склеить ни с одной из последующих, т. к. либо нет контрарных литералов (
), либо их два;
3) 
,
D 
.
Второй этап
На втором этапе определим конъюнкции для обобщенного поглощения .
D .
Таким образом,
.
Третий этап
Так как сокращённая ДНФ не соответствует Теореме 2, т. е. имеет отрицания переменных, то для нахождения минимальной формы ДНФ будем строить импликантную матрицу.
Для этого с помощью СДНФ определим те наборы значений переменных, на которых булева функция равна единице.
Итак, если простая импликанта покрывает некоторую единицу функции, то в соответствующем столбце поставим крестик ´.
импликанты | 1011 | 1010 | 1001 | 1000 | 0100 | 0000 | 0011 | 1101 | 0101 |
| ´ | ´ | ´ | ´ | |||||
| ´ | ´ | |||||||
| ´ | ´ | |||||||
| ´ | ´ | |||||||
| ´ | ´ |
наборы
В любую тупиковую ДНФ обязательно войдут те простые импликанты, которые содержат единственную пометку в некотором столбце. В нашем случае четвёртую импликанту можно исключить. Единственная тупиковая ДНФ является, очевидно, также и минимальной ДНФ:
.
VI. Найти сокращённую ДНФ для функции с вектором значений 
с помощью карт Карно.
Вектор значений соответствует таблице истинности:
xyzu | f(x, y, z, u) | xyzu | f(x, y, z, u) |
0000 | 1 | 1000 | 1 |
0001 | 1 | 1001 | 1 |
0010 | 1 | 1010 | 1 |
0011 | 0 | 1011 | 0 |
0100 | 0 | 1100 | 0 |
0101 | 1 | 1101 | 1 |
0110 | 0 | 1110 | 0 |
0111 | 1 | 1111 | 1 |
Заполнение карт Карно значениями конкретной булевой функции происходит так же, как и таблицы истинности. Но, так как для нахождения простых импликант нужны только наборы, на которых функция f = 1, то значение 0 не отмечаем. Затем выберем литерал (переменную булевой функции) с отрицанием или без отрицания, и определим соответствующую ему площадь.
Конъюнкция выбранных литералов покрывает те клетки, которые находятся на пересечении площадей, покрываемых каждым из литералов, входящих в конъюнкцию.
При нахождении простых импликант необходимо учитывать, что верхний и нижний ряды клеток рассматриваются как соседние. Аналогично – левый и правый вертикальные столбцы клеток.
Окончательно находим все простые импликанты и записываем сокращенную ДНФ функции:
|
= 
.
(все импликанты выделены в табл. овалами).
Заметим, что последняя импликанта покрывает клетки, которые уже покрыты ранее найденными импликантами, и поэтому является лишней. Следовательно, минимальная ДНФ, представленной функции имеет вид:
= .
ЛИТЕРАТУРА
1. , Г. Математическая логика. Курс лекций. Задачник-практикум и решения. Учебное пособие. 3-е изд., испр. СПб.: Лань, 2008.
2. А. Дискретная математика для программистов. – СПб: Питер, 2002.
3. Е. Дискретная математика: логика, группы, графы, фракталы. –М., Издатель АКИМОВА, 2005.
4. , Задачи и упражнения по дискретной математике: Учебное пособие. -3-е изд., перераб. –М.: ФИЗМАТЛИТ, 2006.
