Алгебра логики Скачать
презентацию
<<  Алгебра высказываний Логические операции  >>
Булевы функции и алгебра логики
Булевы функции и алгебра логики
Построить таблицу истинности
Построить таблицу истинности
Фото из презентации «Булевы функции» к уроку алгебры на тему «Алгебра логики»

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

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

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

содержание презентации «Булевы функции»
Сл Текст Эф Сл Текст Эф
1Булевы функции и алгебра логики. Двойственность0 12функция. 12.0
булевых функций. Компьютерная дискретная математика. 13Пример. Найти порядковый номер функции f(x,y),0
Лекции 4-5 Н.В. Белоус. Факультет компьютерных наук принимающей следующие значения: f(0,0)=1, f(0,1)=1,
Кафедра ПО ЭВМ, ХНУРЭ. ХНУРЭ, кафедра ПО ЭВМ, Тел. f(1,0)=0, f(1,1)=1. Двоичный код, соответствующий
7021-446, e-mail: belous@kture.Kharkov.ua. значению этой функции – 1101. 11012 = 1?23 + 1?22 +
2Тема 1 Булевы функции и алгебра логики.0 0?21 + 1?20 = =8+4+0+1=1310 Таким образом f13(x,y) =
3Булевы переменные и функции. Переменные, которые0 (1101)2. x. y. f(x,y). 0. 0. 1. 0. 1. 1. 1. 0. 0. 1. 1.
могут принимать значения только из множества B={0,1}, 1. 13.
называются логическими или булевыми переменными. Сами 14Пример. Построить таблицу истинности для функции18
значения 0 и 1 булевых переменных называются булевыми f198. x. y. z. f (x,y,z). 1. 0. 0. 0. 0. 0. 1. 1. 0. 0.
константами. 3. 1. 0. 0. 0. 1. 1. 0. 1. 0. 0. 1. 1. 0. 1. 1. 1. 1. 0.
4Булевы переменные и функции. Функция вида0 0. 1. 1. 1. Пример заполнения таблицы истинности. 14.
y=f(x1,x2,...,xn), аргументы и значения которой заданы 15Способы задания булевых функций. III. Задание0
на множестве B, называется n-местной булевой функцией. булевых функций с помощью формул Формула – это
Такие функции также называют логическими или выражение, задающее некоторую функцию в виде
переключательными функциями. 4. суперпозиции других функций. Суперпозицией называется
5Основные определения. Кортеж (x1,x2,…,xn)0 прием получения новых функций путем подстановки
конкретных значений булевых переменных называется значений одних функций вместо значений аргументов
двоичным словом (n-словом) или булевым набором длины n. других функций. 15.
Для булевой функции y=f(x1,x2,…,xn) конкретное 16Пример. Рассмотрим формулу булевой алгебры,0
(индивидуальное) значение булевого набора (x1,x2,…,xn) задающую некоторую функцию f(x,y,z) Эта формула
называется также интерпретацией булевой функции f. содержит функции: g(x1) – отрицание, s(x1,x2) –
Множество всех двоичных слов, обозначаемое через Bn, конъюнкция, l(x1,x2) – дизъюнкция. Представим данную
образует область определения булевой функций и формулу в виде суперпозиции указанных функций следующим
называется n-мерным булевым кубом и содержит 2n образом: f (x,y,z) = l(s(x,g(y)),z). 16.
элементов-слов: |Bn|=2n. Каждому двоичному слову 17–. ? ? ? ~. Приоритет выполнения операций. Если в9
соответствует одно из двух возможных значений (0 или формуле отсутствуют скобки, то операции выполняются в
1), таким образом, область значений представляет собой следующей последовательности: Отрицание. Конъюнкция.
кортеж длиной 2n, состоящий из 1 и 0. 5. Дизъюнкция. Импликация. Эквивалентность. Пример Убрать
6Способы задания булевых функций. I. Таблицы0 все возможные скобки Расставить скобки с учетом
истинности Таблицы, в которых каждой интерпретации приоритета операций. 17.
функции поставлено в соответствие ее значение, 18Эквивалентные формулы. Формулы, представляющие одну0
называются таблицами истинности булевой функции. В и ту же функцию, называются эквивалентными или
таблице истинности каждой переменной и значению самой равносильными. 18.
функции соответствует по одному столбцу, а каждой 19Законы и тождества алгебры логики. 1)0
интерпретации — по одной строке. Количество строк в Коммутативность конъюнкции и дизъюнкции x?y = y?x
таблице соответствует количеству различных Доказательство x?y = y?x Доказательство 2)
интерпретаций функции. 6. Ассоциативность конъюнкции и дизъюнкции x?(y?z)=
7Булевы функции одной переменной. ?0? 0 — функция0 (x?y)?z Доказательство x?(y?z)=(x?y)?z Доказательство
константа 0, ?1 = x — функция повторения аргумента, ?2 3) Дистрибутивность конъюнкции и дизъюнкции
= — функция инверсии или отрицания аргумента, ?3 ? 1 — относительно друг друга x?(y?z) = (x?y)?(x?z)
функция константа 1. 7. Доказательство x?(y?z) = (x?y)?(x?z) Доказательство.
8Булевы функции двух переменных. x. y. f0. f1. f2.0 19.
f3. f4. f5. f6. f7. f8. f9. f10. f11. f12. f13. f14. 20Законы и тождества алгебры логики. 4)7
f15. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 1. Идемпотентность конъюнкции и дизъюнкции x?x = x?x = 5)
1. 0. 1. 0. 0. 0. 0. 1. 1. 1. 1. 0. 0. 0. 0. 1. 1. 1. Закон исключенного третьего Доказательство 6) Закон
1. 1. 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. противоречия Доказательство 8) Закон элиминации x?(x?y)
1. 1. 1. 0. 1. 0. 1. 0. 1. 0. 1. 0. 1. 0. 1. 0. 1. 0. = Доказательство x?(x?y) = Доказательство. x. x. 1. 0.
1. 8. x. x. 20.
9Булевы функции двух переменных. 9. Функ- ция. Обоз-0 21Законы и тождества алгебры логики. 7) Тождества с6
начение. Название. Другие обоз-я. Прочтение. f0(x,y). константами. x?0 = x?1 = x?1 = x?0 = 9) Закон двойного
0. Константа 0. Константа 0. f1(x,y). x?y. Конъюнкция отрицания. 10) Законы де Моргана. Доказательство
(логическое «и»). X и y. f2(x,y). Отрицание импликации. Доказательство. x. x. 1. 0. x. 21.
X и не y. f3(x,y). x. Повторение первого аргумента. Как 22Тема 2 Двойственность булевых функций.0
x. f4(x,y). Отрицание обратной импликации. Не x и y. 23Функция f*(x1,…,xn) называется двойственной к0
f5(x,y). Y. Повторение второго аргумента. Как y. функции f(x1,…,xn), если Пример построения двойственной
f6(x,y). x?y. Исключающее «или» (сумма по модулю 2). X функции. Двойственные булевы функции. Пример Найти
не как y. f7(x,y). x?y. Дизъюнкция (логическое «или»). двойственные функции. 23.
X или у. ·, &, &&,*, И, ?, AND, min. > 24Самодвойственные булевы функции. Функция, равная0
< ?, < >, > <, !=, XOR. OR, ИЛИ, +, max. своей двойственной, называется самодвойственной. f =
10Булевы функции двух переменных. 10. Функ- ция.0 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)=
f8(x,y). x?y. отрицание дизъюнкции (стрелка Пирса). Не (1,0). 0. 1. f(0,1). (1,0). 1. 0. f(1,0)= (0,1). 1. 0.
x и не y. f9(x,y). x?y. Эквивалентность. X как y. f(1,0). (0,1). 1. 1. f(1,1)= (0,0). 1. 1. f(1,1).
f10(x,y). Отрицание второго аргумента. Не y. f11(x,y). (0,0). 24.
x?y. Обратная импликация. X, если y (x или не y). 25Пример. Является ли функция f(x,y,z)2
f12(x,y). Отрицание первого аргумента. Не x. f13(x,y). самодвойственной? x. y. z. f (x,y,z). f* (x,y,z). 0. 0.
x?y. Импликация. Если x, то y (не x или y). f14(x,y). x 0. 0. 0. 0. 0. 1. 1. 1. 0. 1. 0. 0. 1. 0. 1. 1. 1. 1.
| y. отрицание конъюнкции (штрих Шеффера). Не x или не 1. 0. 0. 0. 0. 1. 0. 1. 0. 1. 1. 1. 0. 0. 0. 1. 1. 1.
y. f15(x,y). 1. Константа 1. Константа 1. ?, ?, Eqv, =. 1. 1. f(x,y,z) —. Несамодвойственная. 25.
?y. ? ?x. ?, ?, Imp. 26Принцип двойственности. Пусть функция F заданна0
11Способы задания булевых функций. II. Номера булевых0 суперпозицией функций f0,…,fn, где n?N. Функцию F*,
функций и интерпретаций Каждой функции присваивается двойственную F, можно получить, заменив в формуле F
порядковый номер в виде натурального числа, двоичный функции f0,…,fn на двойственные им f0*,…,fn*. 26.
код которого представляет собой столбец значений 27Правило получения двойственных формул. Для того0
функции в таблице истинности. Младшим разрядом чтобы получить двойственную формулу булевой алгебры
считается самая нижняя строка (значение функции на необходимо заменить в ней все конъюнкции на дизъюнкции,
интерпретации (1,1,…,1)), а старшим — самая верхняя дизъюнкции на конъюнкции, 0 на 1, 1 на 0, и
(значение функции на интерпретации (0,0,…,0)). 11. использовать скобки, где необходимо, чтобы порядок
12Способы задания булевых функций. Каждой0 выполнения операций остался прежним. 27.
интерпретации булевой функции присваивается свой номер 28Правило получения двойственных формул. Пример Найти7
– значение двоичного кода, который представляет собой функцию, двойственную функции Решение. 28.
интерпретация. Интерпретации, записанной в верхней 29Правило получения двойственных формул. Если функции0
строке таблицы истинности, присваивается номер 0, затем равны, то и двойственные им функции также равны. Пусть
следует интерпретация номер 1 и т.д. В самой нижней f1 и f2 – некоторые функции, заданные формулами. Тогда
строке расположена интерпретация с номером 2n–1, где n если f1 = f2 , то f1* = f2*. 29.
— количество переменных, от которых зависит булева
29 «Булевы функции» | Булевы функции 49
http://900igr.net/fotografii/algebra/Bulevy-funktsii/Bulevy-funktsii.html
cсылка на страницу
Урок

Алгебра

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