Алгебра логики Скачать
презентацию
<<  Алгебра высказываний Логические операции  >>
Булевы функции и алгебра логики
Булевы функции и алгебра логики
Булевы функции
Булевы функции
Булевы переменные и функции
Булевы переменные и функции
Функция
Функция
Основные определения
Основные определения
Способы задания булевых функций
Способы задания булевых функций
Булевы функции одной переменной
Булевы функции одной переменной
Булевы функции двух переменных
Булевы функции двух переменных
Название
Название
Прочтение
Прочтение
Булевы функции
Булевы функции
Значение двоичного кода
Значение двоичного кода
Порядковый номер функции
Порядковый номер функции
Построить таблицу истинности
Построить таблицу истинности
Задание булевых функций
Задание булевых функций
Формула содержит функции
Формула содержит функции
Приоритет выполнения операций
Приоритет выполнения операций
Эквивалентные формулы
Эквивалентные формулы
Законы и тождества алгебры логики
Законы и тождества алгебры логики
Идемпотентность конъюнкции и дизъюнкции
Идемпотентность конъюнкции и дизъюнкции
Тождества с константами
Тождества с константами
Двойственность булевых функций
Двойственность булевых функций
Пример построения двойственной функции
Пример построения двойственной функции
Самодвойственные булевы функции
Самодвойственные булевы функции
Является ли функция f(x,y,z) самодвойственной
Является ли функция f(x,y,z) самодвойственной
Принцип двойственности
Принцип двойственности
Правило получения двойственных формул
Правило получения двойственных формул
Найти функцию
Найти функцию
Функции равны
Функции равны
Слайды из презентации «Булевы функции» к уроку алгебры на тему «Алгебра логики»

Автор: Настенька. Чтобы увеличить слайд, нажмите на его эскиз. Чтобы использовать презентацию на уроке, скачайте файл «Булевы функции.pps» бесплатно в zip-архиве размером 503 КБ.

Скачать презентацию

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

содержание презентации «Булевы функции.pps»
СлайдТекст
1 Булевы функции и алгебра логики

Булевы функции и алгебра логики

Двойственность булевых функций.

Компьютерная дискретная математика

Лекции 4-5 Н.В. Белоус

Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ

ХНУРЭ, кафедра ПО ЭВМ, Тел. 7021-446, e-mail: belous@kture.Kharkov.ua

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

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

Тема 1 Булевы функции и алгебра логики.

3 Булевы переменные и функции

Булевы переменные и функции

Переменные, которые могут принимать значения только из множества B={0,1}, называются логическими или булевыми переменными. Сами значения 0 и 1 булевых переменных называются булевыми константами.

3

4 Функция

Функция

Булевы переменные и функции.

Функция вида y=f(x1,x2,...,xn), аргументы и значения которой заданы на множестве B, называется n-местной булевой функцией. Такие функции также называют логическими или переключательными функциями.

4

5 Основные определения

Основные определения

Кортеж (x1,x2,…,xn) конкретных значений булевых переменных называется двоичным словом (n-словом) или булевым набором длины n. Для булевой функции y=f(x1,x2,…,xn) конкретное (индивидуальное) значение булевого набора (x1,x2,…,xn) называется также интерпретацией булевой функции f. Множество всех двоичных слов, обозначаемое через Bn, образует область определения булевой функций и называется n-мерным булевым кубом и содержит 2n элементов-слов: |Bn|=2n. Каждому двоичному слову соответствует одно из двух возможных значений (0 или 1), таким образом, область значений представляет собой кортеж длиной 2n, состоящий из 1 и 0.

5

6 Способы задания булевых функций

Способы задания булевых функций

I. Таблицы истинности Таблицы, в которых каждой интерпретации функции поставлено в соответствие ее значение, называются таблицами истинности булевой функции. В таблице истинности каждой переменной и значению самой функции соответствует по одному столбцу, а каждой интерпретации — по одной строке. Количество строк в таблице соответствует количеству различных интерпретаций функции.

6

7 Булевы функции одной переменной

Булевы функции одной переменной

?0? 0 — функция константа 0, ?1 = x — функция повторения аргумента, ?2 = — функция инверсии или отрицания аргумента, ?3 ? 1 — функция константа 1.

7

8 Булевы функции двух переменных

Булевы функции двух переменных

x

y

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

8

9 Название

Название

Булевы функции двух переменных.

9

Функ- ция

Обоз- начение

Название

Другие обоз-я

Прочтение

f0(x,y)

0

Константа 0

Константа 0

f1(x,y)

x?y

Конъюнкция (логическое «и»)

X и y

f2(x,y)

Отрицание импликации

X и не y

f3(x,y)

x

Повторение первого аргумента

Как x

f4(x,y)

Отрицание обратной импликации

Не x и y

f5(x,y)

Y

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

Как y

f6(x,y)

x?y

Исключающее «или» (сумма по модулю 2)

X не как y

f7(x,y)

x?y

Дизъюнкция (логическое «или»)

X или у

·, &, &&,*, И, ?, AND, min

>

<

?, < >, > <, !=, XOR

OR, ИЛИ, +, max

10 Прочтение

Прочтение

Булевы функции двух переменных.

10

Функ- ция

Обоз- начение

Название

Другие обоз-я

Прочтение

f8(x,y)

x?y

отрицание дизъюнкции (стрелка Пирса)

Не x и не y

f9(x,y)

x?y

Эквивалентность

X как y

f10(x,y)

Отрицание второго аргумента

Не y

f11(x,y)

x?y

Обратная импликация

X, если y (x или не y)

f12(x,y)

Отрицание первого аргумента

Не x

f13(x,y)

x?y

Импликация

Если x, то y (не x или y)

f14(x,y)

x | y

отрицание конъюнкции (штрих Шеффера)

Не x или не y

f15(x,y)

1

Константа 1

Константа 1

?, ?, Eqv, =

?y

?

?x

?, ?, Imp

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

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

Способы задания булевых функций.

II. Номера булевых функций и интерпретаций Каждой функции присваивается порядковый номер в виде натурального числа, двоичный код которого представляет собой столбец значений функции в таблице истинности. Младшим разрядом считается самая нижняя строка (значение функции на интерпретации (1,1,…,1)), а старшим — самая верхняя (значение функции на интерпретации (0,0,…,0)).

11

12 Значение двоичного кода

Значение двоичного кода

Способы задания булевых функций.

Каждой интерпретации булевой функции присваивается свой номер – значение двоичного кода, который представляет собой интерпретация. Интерпретации, записанной в верхней строке таблицы истинности, присваивается номер 0, затем следует интерпретация номер 1 и т.д. В самой нижней строке расположена интерпретация с номером 2n–1, где n — количество переменных, от которых зависит булева функция.

12

13 Порядковый номер функции

Порядковый номер функции

Пример.

Найти порядковый номер функции f(x,y), принимающей следующие значения: f(0,0)=1, f(0,1)=1, f(1,0)=0, f(1,1)=1.

Двоичный код, соответствующий значению этой функции – 1101. 11012 = 1?23 + 1?22 + 0?21 + 1?20 = =8+4+0+1=1310 Таким образом f13(x,y) = (1101)2

x

y

f(x,y)

0

0

1

0

1

1

1

0

0

1

1

1

13

14 Построить таблицу истинности

Построить таблицу истинности

Пример.

Построить таблицу истинности для функции f198

x

y

z

f (x,y,z)

1

0

0

0

0

0

1

1

0

0

1

0

0

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

Пример заполнения таблицы истинности

14

15 Задание булевых функций

Задание булевых функций

Способы задания булевых функций.

III. Задание булевых функций с помощью формул Формула – это выражение, задающее некоторую функцию в виде суперпозиции других функций. Суперпозицией называется прием получения новых функций путем подстановки значений одних функций вместо значений аргументов других функций.

15

16 Формула содержит функции

Формула содержит функции

Пример.

Рассмотрим формулу булевой алгебры, задающую некоторую функцию f(x,y,z) Эта формула содержит функции: g(x1) – отрицание, s(x1,x2) – конъюнкция, l(x1,x2) – дизъюнкция. Представим данную формулу в виде суперпозиции указанных функций следующим образом: f (x,y,z) = l(s(x,g(y)),z)

16

17 Приоритет выполнения операций

Приоритет выполнения операций

–.

?

?

?

~

Приоритет выполнения операций

Если в формуле отсутствуют скобки, то операции выполняются в следующей последовательности: Отрицание. Конъюнкция. Дизъюнкция. Импликация. Эквивалентность

Пример Убрать все возможные скобки Расставить скобки с учетом приоритета операций

17

18 Эквивалентные формулы

Эквивалентные формулы

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

18

19 Законы и тождества алгебры логики

Законы и тождества алгебры логики

1) Коммутативность конъюнкции и дизъюнкции x?y = y?x Доказательство x?y = y?x Доказательство 2) Ассоциативность конъюнкции и дизъюнкции x?(y?z)= (x?y)?z Доказательство x?(y?z)=(x?y)?z Доказательство 3) Дистрибутивность конъюнкции и дизъюнкции относительно друг друга x?(y?z) = (x?y)?(x?z) Доказательство x?(y?z) = (x?y)?(x?z) Доказательство

19

20 Идемпотентность конъюнкции и дизъюнкции

Идемпотентность конъюнкции и дизъюнкции

Законы и тождества алгебры логики.

4) Идемпотентность конъюнкции и дизъюнкции x?x = x?x = 5) Закон исключенного третьего Доказательство 6) Закон противоречия Доказательство 8) Закон элиминации x?(x?y) = Доказательство x?(x?y) = Доказательство

x

x

1

0

x

x

20

21 Тождества с константами

Тождества с константами

Законы и тождества алгебры логики.

7) Тождества с константами. x?0 = x?1 = x?1 = x?0 = 9) Закон двойного отрицания. 10) Законы де Моргана. Доказательство Доказательство

x

x

1

0

x

21

22 Двойственность булевых функций

Двойственность булевых функций

Тема 2 Двойственность булевых функций.

23 Пример построения двойственной функции

Пример построения двойственной функции

Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если Пример построения двойственной функции.

Двойственные булевы функции

Пример Найти двойственные функции

23

24 Самодвойственные булевы функции

Самодвойственные булевы функции

Функция, равная своей двойственной, называется самодвойственной. f = f*

x

y

f(x,y)

f*(x,y)

x

y

f(x,y)=f*(x,y)

0

0

f(0,0)

(1,1)

0

0

f(0,0)= (1,1)

0

1

f(0,1)= (1,0)

0

1

f(0,1)

(1,0)

1

0

f(1,0)= (0,1)

1

0

f(1,0)

(0,1)

1

1

f(1,1)= (0,0)

1

1

f(1,1)

(0,0)

24

25 Является ли функция f(x,y,z) самодвойственной

Является ли функция f(x,y,z) самодвойственной

Пример.

Является ли функция f(x,y,z) самодвойственной?

x

y

z

f (x,y,z)

f* (x,y,z)

0

0

0

0

0

0

0

1

1

1

0

1

0

0

1

0

1

1

1

1

1

0

0

0

0

1

0

1

0

1

1

1

0

0

0

1

1

1

1

1

f(x,y,z) —

Несамодвойственная

25

26 Принцип двойственности

Принцип двойственности

Пусть функция F заданна суперпозицией функций f0,…,fn, где n?N. Функцию F*, двойственную F, можно получить, заменив в формуле F функции f0,…,fn на двойственные им f0*,…,fn*.

26

27 Правило получения двойственных формул

Правило получения двойственных формул

Для того чтобы получить двойственную формулу булевой алгебры необходимо заменить в ней все конъюнкции на дизъюнкции, дизъюнкции на конъюнкции, 0 на 1, 1 на 0, и использовать скобки, где необходимо, чтобы порядок выполнения операций остался прежним.

27

28 Найти функцию

Найти функцию

Правило получения двойственных формул.

Пример Найти функцию, двойственную функции Решение

28

29 Функции равны

Функции равны

Правило получения двойственных формул.

Если функции равны, то и двойственные им функции также равны. Пусть f1 и f2 – некоторые функции, заданные формулами. Тогда если f1 = f2 , то f1* = f2*

29

«Булевы функции»
http://900igr.net/prezentatsii/algebra/Bulevy-funktsii/Bulevy-funktsii.html
cсылка на страницу
Урок

Алгебра

34 темы
Слайды
Презентация: Булевы функции.pps | Тема: Алгебра логики | Урок: Алгебра | Вид: Слайды