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

Сентябрь 13, 2022

Главная
Математика
Булевы функции и алгебра логики. Двойственность булевых функций

Содержание

2. Тема 1 Булевы функции и алгебра логики
3. Булевы переменные и функции Переменные, которые могут принимать значения только из множества B={0,1}, называются логическими или
4. Булевы переменные и функции Функция вида y=f(x1,x2,...,xn), аргументы и значения которой заданы на множестве B, называется
5. Основные определения Кортеж (x1,x2,…,xn) конкретных значений булевых переменных называется двоичным словом (n-словом) или булевым набором длины
6. Способы задания булевых функций I. Таблицы истинности Таблицы, в которых каждой интерпретации функции поставлено в соответствие
7. Булевы функции одной переменной ϕ0≡ 0 — функция константа 0, ϕ1 = x — функция повторения
8. Булевы функции двух переменных
9. Булевы функции двух переменных
10. Булевы функции двух переменных
11. Способы задания булевых функций II. Номера булевых функций и интерпретаций Каждой функции присваивается порядковый номер в
12. Способы задания булевых функций Каждой интерпретации булевой функции присваивается свой номер – значение двоичного кода, который
13. Пример Найти порядковый номер функции f(x,y), принимающей следующие значения: f(0,0)=1, f(0,1)=1, f(1,0)=0, f(1,1)=1. Двоичный код, соответствующий
14. Пример Построить таблицу истинности для функции f198 Пример заполнения таблицы истинности 0 0 0 0 1
15. Способы задания булевых функций III. Задание булевых функций с помощью формул Формула – это выражение, задающее
16. Пример Рассмотрим формулу булевой алгебры, задающую некоторую функцию f(x,y,z) Эта формула содержит функции: g(x1) – отрицание,
17. Приоритет выполнения операций Если в формуле отсутствуют скобки, то операции выполняются в следующей последовательности: Отрицание. Конъюнкция.
18. Эквивалентные формулы Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными.
19. Законы и тождества алгебры логики 1) Коммутативность конъюнкции и дизъюнкции x∧y = y∧x Доказательство x∨y =
20. Законы и тождества алгебры логики 4) Идемпотентность конъюнкции и дизъюнкции x∨x = x∧x = 5) Закон
21. Законы и тождества алгебры логики 7) Тождества с константами. x∨0 = x∧1 = x∨1 = x∧0
22. Тема 2 Двойственность булевых функций
23. Двойственные булевы функции Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если Пример построения двойственной функции Пример
24. Самодвойственные булевы функции Функция, равная своей двойственной, называется самодвойственной. f = f*
25. Является ли функция f(x,y,z) самодвойственной? Пример f(x,y,z) — несамодвойственная
26. Принцип двойственности Пусть функция F заданна суперпозицией функций f0,…,fn, где n∈N. Функцию F*, двойственную F, можно
27. Для того чтобы получить двойственную формулу булевой алгебры необходимо заменить в ней все конъюнкции на дизъюнкции,
28. Пример Найти функцию, двойственную функции Решение Правило получения двойственных формул
30. Скачать презентацию

Слайд 2

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

Слайд 3

Булевы переменные и функции
Переменные, которые могут принимать значения только из

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

Слайд 4

Булевы переменные и функции
Функция вида y=f(x1,x2,...,xn), аргументы и значения которой заданы

на множестве B, называется n-местной булевой функцией. Такие функции также называют логическими или переключательными функциями.

Слайд 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.

Слайд 6

Способы задания булевых функций
I. Таблицы истинности
Таблицы, в которых каждой интерпретации

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

Слайд 7

Булевы функции одной переменной
ϕ0≡ 0 — функция константа 0,
ϕ1 = x — функция

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

Слайд 8

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

Слайд 9

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

Слайд 10

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

Слайд 11

Способы задания булевых функций
II. Номера булевых функций и интерпретаций
Каждой функции присваивается

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

Слайд 12

Способы задания булевых функций
Каждой интерпретации булевой функции присваивается свой номер –

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

Слайд 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

Слайд 14

Пример
Построить таблицу истинности для функции f198
Пример заполнения таблицы истинности
0
0
0
0
1
1
1
1

Слайд 15

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

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

Слайд 16

Пример
Рассмотрим формулу булевой алгебры, задающую некоторую функцию f(x,y,z)
Эта формула содержит

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

Слайд 17

Приоритет выполнения операций
Если в формуле отсутствуют скобки, то операции выполняются в

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

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

Слайд 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) Доказательство

Слайд 20

Законы и тождества алгебры логики
4) Идемпотентность конъюнкции и дизъюнкции
x∨x =
x∧x =
5)

Закон исключенного третьего
Доказательство
6) Закон противоречия
Доказательство
8) Закон элиминации
x∧(x∨y) = Доказательство
x∨(x∧y) = Доказательство

Слайд 21

Законы и тождества алгебры логики
7) Тождества с константами.
x∨0 =
x∧1

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

Слайд 22

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

Слайд 23

Двойственные булевы функции
Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если

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

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

Слайд 24

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

Слайд 25

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

Слайд 26

Принцип двойственности
Пусть функция F заданна суперпозицией функций f0,…,fn, где n∈N.

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

Слайд 27

Для того чтобы получить двойственную формулу булевой алгебры необходимо заменить в

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

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

Слайд 28

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

Содержание

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

Булевы переменные и функции Переменные, которые могут принимать значения только из

Булевы переменные и функцииФункция вида y=f(x1,x2,...,xn), аргументы и значения которой заданы

Основные определенияКортеж (x1,x2,…,xn) конкретных значений булевых переменных называется двоичным словом (n-словом)

Способы задания булевых функцийI. Таблицы истинности Таблицы, в которых каждой интерпретации

Булевы функции одной переменнойϕ0≡ 0 — функция константа 0,ϕ1 = x — функция

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

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

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

Способы задания булевых функцийII. Номера булевых функций и интерпретацийКаждой функции присваивается

Способы задания булевых функцийКаждой интерпретации булевой функции присваивается свой номер –

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

ПримерПостроить таблицу истинности для функции f198Пример заполнения таблицы истинности00001111

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

ПримерРассмотрим формулу булевой алгебры, задающую некоторую функцию f(x,y,z) Эта формула содержит

Приоритет выполнения операций Если в формуле отсутствуют скобки, то операции выполняются в

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

Законы и тождества алгебры логики1) Коммутативность конъюнкции и дизъюнкции x∧y = y∧x

Законы и тождества алгебры логики4) Идемпотентность конъюнкции и дизъюнкции x∨x = x∧x =5)

Законы и тождества алгебры логики7) Тождества с константами. x∨0 = x∧1

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

Двойственные булевы функции Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если

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

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

Принцип двойственности Пусть функция F заданна суперпозицией функций f0,…,fn, где n∈N.

Для того чтобы получить двойственную формулу булевой алгебры необходимо заменить в

Пример Найти функцию, двойственную функции РешениеПравило получения двойственных формул

Похожие презентации

Булевы переменные и функции
Переменные, которые могут принимать значения только из

Булевы переменные и функции
Функция вида y=f(x1,x2,...,xn), аргументы и значения которой заданы

Основные определения
Кортеж (x1,x2,…,xn) конкретных значений булевых переменных называется двоичным словом (n-словом)

Способы задания булевых функций
I. Таблицы истинности
Таблицы, в которых каждой интерпретации

Булевы функции одной переменной
ϕ0≡ 0 — функция константа 0,
ϕ1 = x — функция

Способы задания булевых функций
II. Номера булевых функций и интерпретаций
Каждой функции присваивается

Способы задания булевых функций
Каждой интерпретации булевой функции присваивается свой номер –

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

Пример
Построить таблицу истинности для функции f198
Пример заполнения таблицы истинности
0
0
0
0
1
1
1
1

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

Пример
Рассмотрим формулу булевой алгебры, задающую некоторую функцию f(x,y,z)
Эта формула содержит

Приоритет выполнения операций
Если в формуле отсутствуют скобки, то операции выполняются в

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

Законы и тождества алгебры логики
1) Коммутативность конъюнкции и дизъюнкции
x∧y = y∧x

Законы и тождества алгебры логики
4) Идемпотентность конъюнкции и дизъюнкции
x∨x =
x∧x =
5)

Законы и тождества алгебры логики
7) Тождества с константами.
x∨0 =
x∧1

Двойственные булевы функции
Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если

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

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

Принцип двойственности
Пусть функция F заданна суперпозицией функций f0,…,fn, где n∈N.

Пример
Найти функцию, двойственную функции
Решение
Правило получения двойственных формул