Булевы функции

Повторение

«Решение логических задач»

1. Вписать в треугольник цифры от 1 до 6, так, чтобы сумма цифр вдоль каждой стороны была равна 9.

2. В авиационном подразделении служат Потапов, Щедрин, Семёнов, Коновалов и Самойлов. Их специальности: пилот, штурман, бортмеханик, радист и синоптик.

Известно:

• Щедрин и Коновалов незнакомы с управлением самолёта;
• Потапов и Коновалов готовятся стать штурманами;
• Квартиры Щедрина и Самойлова находятся рядом с квартирой радиста;
• Семёнов, находясь в доме отдыха, встретил Щедрина и сестру синоптика;
• Потапов и Щедрин в свободное время играют в шахматы с бортмехаником и пилотом;
• Коновалов, Семёнов и синоптик увлекаются боксом;
• Радист боксом не увлекается.

Определить, какую специальность имеет каждый из них?

Щедрин- штурман, Коновалов-бортмеханик,Семёнов-пилот,

Самойлов-синоптик,Потапов-радист.

3. В компании 5 человек: Алексей, Вера, Глеб, Даша и Евгений. На вечеринку:

• Если пригласить Алексея, то необходимо пригласить и Веру;
• Можно пригласить либо Глеба, либо Веру, но не вместе;
• Можно пригласить либо Дашу, либо Евгения, либо их обоих;
• Дашу можно пригласить либо вместе с Глебом, либо ни того, ни другого;
• Если пригласить Евгения, то тогда необходимо пригласить Алексея и Дашу.

Кого все-таки пригласить на вечеринку?

Пригласить нужно Дашу и Глеба.

1. В течение последних четырёх лет Евгений, Фёдор, Дмитрий и Борис, работающие на одном предприятии, получали отпуск в мае, июне, июле и августе. Время их отпусков не совпадало и ни один из них не получил отпуска в один и тот же месяц.

В первый год Дмитрий отдыхал в июле, а второй- в августе.

Во второй год в мае получил Евгений.

На третий год в июне отпуск получил Борис, а на четвёртый год в июле отдыхал Фёдор.

В каком месяце отдыхал Евгений в первый год?

В первый год Евгений отдыхал в июне.

2. В поезде Москва-Санкт-Петербург едут

пассажиры. Иванов, Петров и Сидоров. Такие

же фамилии имеют машинист, помощник

машиниста и бригадир поезда. Известно, что

пассажир Иванов живёт в Москве, бригадир поезда

живёт на полпути от Москвы до Санкт- Петербурга;

пассажир-однофамилец бригадира поезда живёт в

Санкт-Петербурге; тот пассажир, который живёт

ближе к месту жительства бригадира, чем

другие пассажиры, зарабатывает в месяц

ровно втрое больше бригадира; пассажир

Петров зарабатывает в месяц 20.000 рублей;

Сидоров(из бригады) недавно выиграл у

помощника машиниста партию на бильярде.

Как фамилия машиниста?

Машинист-Сидоров, помощник-Иванов, бригадир-Петров

Раздел 1. Алгебра высказываний Тема 1.2.3.Истинностные (булевы) функции

План занятия:

• Изучение теоретического материала.

2. Практическая работа.

3. Самостоятельная работа.

Повторение изученного материала

Построить таблицу истинности для следующих функций:

1.

- константа 0

x 1

1

x 2

1

1

0

0

0

1

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

2.

- штрих Шеффера

x 1

1

x 2

x 1 x 2

1

1

0

0

0

1

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

3.

- повтор x 2

x 2

1

x 2

0

1

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

4.

- стрелка Пирса

x 1

1

x 2

x 1 x 2

1

1

0

0

0

1

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

5.

- правая импликация

x 1

1

x 2

1

1

0

0

0

1

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

6.

- левая импликация

x 1

1

x 2

1

1

0

0

0

1

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

7.

-запрет

-запрет

x 1

x 1

x 2

x 2

1

1

1

1

1

1

0

0

0

0

0

1

1

0

0

0

Повторение изученного материала

Построить таблицу истинности для следующих функций:

8.

- эквивалентность

x 1

1

x 2

x 1 x 2

1

1

0

0

0

1

0

Повторение изученного материала

Через какие логические операции

можно выразить штрих Шеффера и

стрелку Пирса(штрих Лукасевича)?

Проверочная работа «Булевы функции двух переменных»

1. Построить таблицы истинности следующих функций:

Вариант 1:

1)константа 1; 2) левая импликация;

3)Штрих Шеффера; 4) запрет x 1 .

Вариант 2:

1) конъюнкция; 2) стрелка Пирса;

3) повтор x 2 ; 4) отрицание x 1 .

Вариант 3:

1) Сложение по mod 2 ; 2) дизъюнкция;

3) повтор x 1 ; 4) отрицание x 2 .

Вариант 4:

1)константа 0; 2) правая импликация;

3) эквивалентность; 4) запрет x 2 .

Проверочная работа «Булевы функции двух переменных»

2. Построить таблицы истинности следующих функций:

Вариант 1:

Вариант 2:

Вариант 3:

Вариант 4:

СДНФ и СКНФ.

Функция алгебры логики

Функцией алгебры логики n называется

любая функция n переменных

аргументы которой принимают два

значения 0 и 1,

а сама функция принимает одно из двух

значений 1 или 0.

Правила построения СДНФ.

• Для формулы получаем любую ДНФ.
• Из ДНФ получаем СДНФ с помощью:

• Пусть В есть слагаемое ДНФ, не содержащее x i . Тогда надо заменить В на слагаемое
• Если в ДНФ есть два одинаковых слагаемых В и В, то одно отбросить, т. к.

2. Из ДНФ получаем СДНФ с помощью:

3) Если в ДНФ есть ,

то его отбросить.

4) Если в некоторое слагаемое В переменная

входит дважды, то лишнюю отбросить, т. к.

Правила построения СКНФ.

• Для формулы получаем любую КНФ.
• Из КНФ получаем СКНФ с помощью:

• Пусть В есть слагаемое КНФ, не содержащее x i . Тогда надо заменить В на слагаемое
• Если в КНФ есть два одинаковых слагаемых В и В, то одно отбросить, т. к.

2. Из КНФ получаем СКНФ с помощью:

3) Если в КНФ есть ,

то его отбросить.

4) Если в некоторое слагаемое В переменная

входит дважды, то лишнюю отбросить, т. к.

1 .Изучение теоретического материала

Соотнести

СКНФ и СДНФ :

СКНФ

СДНФ

Соотнести

СКНФ и СДНФ :

СКНФ

СДНФ

2. Практическая работа

1. Формулу привести к СДНФ, предварительно приведя её к ДНФ равносильными преобразованиями.

2. Для примера 1 найти СДНФ путем оставления таблицы истинности.

3. Для формулы из примера 1 найти СКНФ, предварительно приведя её к КНФ равносильными преобразованиями.

4. Для формулы из примера 1 найти СКНФ, записав предварительно СДНФ её отрицания, а потом воспользовавшись формулой.

Построение СДНФ и СКНФ.

Задание № 1:

Приведите равносильными

преобразованиями формулу своего

варианта к СДНФ и

проверьте получившийся результат с

помощью таблиц истинности.

Задание №2:

Найти формулу, определяющую функцию

, заданную таблицей истинности.

x

y

1

1

z

1

1

F(x,y,z)

1

1

1

0

1

0

0

0

0

1

0

1

0

0

0

1

1

0

1

0

0

0

1

1

0

1

0

1

3. Самостоятельная работа

• Построить таблицу истинности для булевых функций трёх переменных:

Вариант 1

Вариант 2

Вариант 3

Вариант 4

3.Самостоятельная работа

2 . Проверьте, являются ли булевы функции эквивалентными.

/ построение таблицы истинности или упрощение с помощью равносильностей / .

3 . По заданной функции постройте таблицу истинности, приведите функцию к СКНФ (СДНФ).

/ использовать алгоритм построения

СКНФ, СДНФ / .