Практические задания с решениями

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

1. Упрощение логических функций, заданных различным образом.

2. Построение таблиц истинности функций.

3. Вычисление значения логического выражения для заданного набора значений переменных.

4. Определение тождественности логических функций.

Упрощение логических функций, заданных различным образом

1. Функция задана в произвольной форме.

Пример 1. Упростить логическую функцию, заданную выражением:

Решение:

А. Приведение функции к ДНФ путем использования законов и правил, т.е. .

Б. Вычерчивание конъюнкций, равных нулю.

Конъюнкция , конъюнкции,равны нулю, поэтому получаем упрощенную функцию.

Пример 2. Упростить логическую функцию, заданную выражением:

Решение:

А. Применение закона отрицания с целью последующего перехода к ДНФ, т.е. .

Б. Анализ промежуточного результата. Устанавливаем. Что первая скобка равна единице, т.к. и, где. Окончательно получаем:.

Пример 3. Упростить логическую функцию, заданную выражением:

.

Решение:

А. Упрощение функции путем использования закона отрицания и перенесения скобок:

Б. Применение правила расширения:

- из группы конъюнкций исключаем;

- из группы конъюнкций исключаем;

- из группы конъюнкций исключаем.

Окончательно получаем: .

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

Применяем правило расширения в следующей последовательности:

- из группы конъюнкций исключаем;

- из группы конъюнкций исключаем.

В результате получаем .

Эта функция по рассмотренным правилам и законам упрощению не поддается.

Заметим, что если имеется несколько форм одной функции, которые не поддаются дальнейшим упрощениям, то они называются тупиковыми. Одна из них является минимальной.

2. Функция задана таблицей истинности

Пример 4. Упростить функциюF(, ,) равную единице на наборах 3, 5, 6, 7 (011, 101, 110, 111).

Решение:

А. Построение таблицы истинности.

В первых трех столбцах записываются возможные наборы. В столбце F на наборах 011, 101, 110 и 111 проставляются единицы; на остальных наборах проставляются нули.

Б. Запись функции в СДНФ (см. правило записи).

Наборам 011, 101, 110, 111 соответствуют конъюнкциям ,,,, поэтому функция будет записана в следующем виде:.

В. Упрощение функции.

Функции, записанные в СДНФ, первоначально упрощаются по правилу склеивания. Затем применяются другие правила и тождественные соотношения.

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

После склеивания пар соседних конъюнкций окончательно получим: .

Можно было не подписывать конъюнкцию , а просто склеить поочередно три первые конъюнкции с четвертой конъюнкцией.

Построение таблиц истинности функций

Пример 5. Построить таблицу истинности функции:.

Решение:

А. Запись заданной функции в СДНФ.

Данная функция зависит от трех переменных и записана в ДНФ. Для записи функции в СДНФ первая конъюнкция умножается на выражение , вторая на выражение -. В скобках используются те переменные и их отрицания, которые отсутствуют в конъюнкциях:

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

Так как по правилу записи конъюнкций в СДНФ единице в наборе соответствует переменная, а нулю – ее отрицание, то конъюнкциям ,,,соответствуют наборы 111, 110, 011, 001, т.е. 7,6,3,1.

В. Непосредственное построение таблицы.

В столбце F таблицы на наборах 111, 110, 011, 001 проставляются единицы, а на остальных наборах ставятся нули.

Вычисление значения логического выражения

Для вычисления значения логического выражения на заданном наборе значений переменных можно применять два способа: способ использования СДНФ и способ подстановки.

Пример 6. Вычислить значение логического выражения:при x=1, y=1, z=0, т.е. на наборе 6, или 110.

Решение:

Первый способ.

А. Получение СДНФ заданной функции (см. выше пример 4): .

После исключения повторяющейся конъюнкции получим: .

Б. Определение значения выражения.

Выражение V принимает единичное значение только на наборах 100, 000 и 101, или 4, 0, 5. Так как задан набор 6, то логическое выражение принимает нулевое значение (V=0).

Второй способне нуждается в особых пояснениях. При заданных значениях x=1, y=1 и z=0 имеем=0,=1. Подставляем эти значения в выражение и получаем: V=0•1+1•0=0+0=0.

В случае вычисления значений сложных логических выражений второй способ не исключает ошибок.

Определение тождественности логических функций

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

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

Пример 7. Проверить тождественность логических функций:

Решение:

А. Упрощение функции F.

Применяем закон отрицания и перемножаем скобки, т.е. .

Во второй скобке конъюнкции исклеиваются, поэтому получаем:

Переменная поглощает конъюнкцию, что дает:

или.

Функция F оказалась записанной в СДНФ, так как содержит конъюнкции одинакового ранга, и в них входят все переменные, от которых она зависит.

Б. Преобразование функции f .

. Функция f также записана в СДНФ.

Так как СДНФ функций F и f не совпадают, то они не являются тождественными.

В. Преобразование функции P.

. Получена СДНФ функции P.

Функции F и P являются тождественными, так как имеют одинаковые СДНФ.

Пример 8. Проверить тождественность логических функций F и f.

.

принимает единичные значения на наборах 2, 3.

Решение:

А. Упрощение функции F.

Применяется закон отрицания: .

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

Во второй скобке используется правило свертки, и затем скобки перемножаются:

.

Б. Получение СДНФ функции F.

.

В. Получение СДНФ функции f.

Так как функции f принимает единичные значения на наборах 2 и 3, то ее СДНФ будет иметь вид .

Функции F и f имеют одинаковые СДНФ, следовательно, они тождественны.

Пример 9. Проверить тождественность логических функций:

и.

Решение:

Функция f имеет следующую минимальную форму: .

А. Упрощение функции F:

- перемножение скобок

- исключение лишней конъюнкции из группы;

- исключение лишней конъюнкции yz из группы .

В результате получаем: .

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

Б. Получение СДНФ функции F.

После удаления повторяющихся конъюнкций получаем:

В. Получение СДНФ функции f.

.

Функции F и f имеют одинаковые СДНФ и принимают единичные значения на одних и тех же наборах 0, 1, 2, 3, 4, 5, 6, 7. Эти функции тождественны. Так как минимальные формы функций не совпадают, то можно сделать вывод, что для функции F была получена тупиковая форма.

Пример 10. Три множества A={a, b, c}, B={0, 1}, C={1, 5, c} заданы перечислением элементов. Определить множество D, являющееся решениемD=(AB)C.

1) {c, 1};

2) {a, b, 1};

3) {c, 1, 5};

4) {1};

5) {Ø}.

Решение:

Построим множество D = (A B)C. Выполним операции по шагам.

А. A B= {a,b,c}{0, 1} = {Ø}, т.к. нет общих элементов.

Б Б. (AB)C= {Ø}{1, 5,c} = {Ø},, т. к. нет общих элементов.

Ответ: 5).

Пример 11.. Укажите, при каких значениях x, y, p истинно следующее выражение:

(p и (x-1 < y) или не (x >= y)).

1) x=7, y=6, p=нет;

2) x=7, y=6, p=да;

3) x=7, y=7, p=нет;

4) x=4, y=6, p=да;

5) x=6, y=4, p=да.

Решение:

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

2 1 5 4 3

(p и (x-1 < y) или не (x >= y)).

Б. Составим таблицу истинности для каждого варианта ответа.

№ вар.	x	y	p	x>=y	Не (x>=y)	(x-1)<y	P и (x-1)<y	(p и (x-1)<y) или не (x>=y))
1.	7	6	Нет	7>=6 да	Нет	(7-1)<6 нет	Нет и нет =нет	Нет или нет =нет
2.	7	6	Да	7>=6 да	Нет	(7-1)<6 нет	Да и нет =нет	Нет или нет =нет
3.	7	7	Нет	7>=7 да	Нет	(7-1)<7 да	Нет и да =нет	Нет или нет =нет
4.	4	6	Да	4>=6 нет	Да	(4-1)<6 да	Да и да = да	Да или да = да
5.	6	4	Да	6>=4 да	Нет	(6-1)<4 нет	Да и нет =нет	Нет или нет =нет

Ответ: 4)

Пример 12.Укажите, при каких значениях x, y, z, ложно следующее выражение: (не z или (y и x)) и (не x или y).

1) x=1, y=1, z=1;

2) x=0, y=1, z=0;

3) x=1, y=0, z=1;

4) x=0, y=0, z=0;

5) x=1, y=1, z=0.

Решение:

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

2 3 1 6 4 5

(не z или (y и x)) и (не x или y).

Б. Составим таблицу истинности для каждого варианта ответа.

№ вар.	x	y	z	y и x	не z	не z или (y и x)	не x	не x или y	(не z или (y и x)) и (не x или y)
1.	1	1	1	1	0	0 или 1 = 1	0	0 или 1 = 1	1 и 1 = 1
2.	0	1	0	0	1	1 или 0 = 1	1	1 или 1 = 1	1 и 1 = 1
3.	1	0	1	0	0	0 или 0 = 0	0	0 или 0 = 0	0 и 0 = 0
4.	0	0	0	0	1	1 или 0 = 1	1	1 или 0 = 1	1 и 1 = 1
5.	1	1	0	1	1	1 или 1 = 1	0	0 или 1 = 1	1 и 1 = 1

Ответ: 3)

Решение задач с помощью кругов Эйлера

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

Для обозначения логической операции «ИЛИ» в запросе используется символ , а для логической операции «И» - &.

А	волейбол баскетболподача
Б	волейбол баскетболподачаблок
В	волейбол баскетбол
Г	волейбол &баскетбол&подача

Решение.

Способ 1.Связка И между двумя словами в поисковом запросе означает, что требуется найти web-страницы, содержащие одновременно и первое, и второе слово. Связка ИЛИ – что ищутся страницы, включающие хотя бы одно из указанных слов. Поэтому больше всего страниц будет найдено по запросу Б, т.к. в искомое множество страниц попадут все страницы, каждая из которых содержит хотя бы одно (любое) слово из поискового запроса.

Меньше всего страниц будет найдено по запросу Г, поскольку он требует присутствия на искомой странице всех трех слов одновременно.

По запросу А будет найдено больше страниц, чем по запросу В, из-за этого в результате запроса А войдут страницы, содержащие слово «подача», которые не попадут в результате выполнения запроса В, если в них не будет слов «волейбол» и «баскетбол». Так, например, если на странице есть словосочетание «подача в теннисе», но нет ни слова про волейбол и баскетбол, то она будет найдена по запросам А и Б, но не будет найдена по запросам В и Г.

Ответ: ГВАБ.

Способ 2.Рассмотрим множества web-страниц, содержащие каждое из искомых слов. Запросу X&X будет соответствовать пересечение множеств X и Y, а запросу XY – их объединение. Воспользуемся графическим представлением действий над множествами (кругами Эйлера). Множество страниц, содержащих некоторое слово, будем обозначать кругом. Множество, получившееся в результате запроса, будем закрашивать серым цветом.

Диаграмма для запроса А будет выглядеть следующим образом:

Диаграмма для запроса Б будет выглядеть следующим образом:

Диаграмма для запроса В будет выглядеть следующим образом:

Диаграмма для запроса Г будет выглядеть следующим образом:

Получается, что результаты запроса возрастают в порядке ГВАБ.

Ответ:ГВАБ.