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

Август 7, 2022

Главная
Математика
Булевы функции

Содержание

2. Введение Постиндустриальное общество, в котором мы живем, постепенно преобразуется в информационное. Напомню, что информационное общество –
3. ДЖОРДЖ БУЛЬ (1815 – 1864) Создателем алгебры логики является живший в ХIХ веке английский математик Джордж
4. Булевой алгеброй Алгеброй Буля называется непустое множество A с двумя бинарными операциями (конъюнкция, И), (дизъюнкция, ИЛИ),
5. Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n переменных, аргументы которой x1, x2,
6. Геометрическое представление логических функций Функцию 2-х переменных можно представить на плоскости в декартовой системе координат. Две
7. Геометрическое представление логических функций Функцию 3-х переменных можно представить в 3-мерном пространстве декартовой системы координат в
8. Геометрическое представление логических функций Функцию 4-х переменных представляют в виде 4-мерного куба.
9. Практически все булевы функции малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные
10. Таблица значений булевых функций от одной переменной:
11. Названия булевых функций от одной переменной:
12. Легко, не правда ли? Даже человек, который первый раз видит материал, составит таблицу за минуту, как
13. Ниже представлен скриншот программы, рассчитавшей таблицу значений для отрицания дизъюнкции Т.е. от пользователя требуется только ввести
14. Чуть выше мы рассмотрели само понятие булевой функции от n переменных. А сколько всего может быть
15. Предположим, что есть F(X1, X2, X3) . Известна ее таблица истинности:
17. Скачать презентацию

Слайд 2

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

что информационное общество – это историческая фаза развития цивилизации, в которой главными продуктами производства становятся информация и знания. Огромное место в нашей жизни теперь занимает скорость получения и обработки информации. Чрезвычайно важна ее актуальность. И на фоне всего сказанного очень контрастирует тот факт, что решение многих задач в обучении студенты вынуждены реализовывать «на листочке». Хотя задачи являются алгоритмическими, легко программируемыми, быстро решаемыми на современных ПК. На мой взгляд обучаемый должен понять только принцип решения. Здесь приводятся две программы, связанных с изучением булевых функций.

Слайд 3

ДЖОРДЖ БУЛЬ (1815 – 1864)

Создателем алгебры логики является живший

в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний.

Слайд 4

Булевой алгеброй
Алгеброй Буля называется непустое множество A
с двумя бинарными

операциями (конъюнкция, И), (дизъюнкция, ИЛИ), унарной операцией (инверсия, НЕ) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:
ассоциативность
коммутативность
законы поглощения
дистрибутивность
дополнительность

Слайд 5

Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n

переменных, аргументы которой x1, x2, ... , xn и сама функция f принимают значения 0 или 1 , т. е. xi {0, 1}, i = 1, 2, ... , n; f (x1, x2, ... , xn) {0, 1}.

Слайд 6

Геометрическое представление логических функций
Функцию 2-х переменных можно представить на плоскости в

декартовой системе координат.
Две вершины, принадлежащие одному и тому же ребру, называются соседними и «склеиваются» по переменной, меняющейся вдоль этого ребра.

«склеивание» по х

Слайд 7

Геометрическое представление логических функций
Функцию 3-х переменных можно представить в 3-мерном пространстве

декартовой системы координат в виде 3-мерного куба.

Слайд 8

Геометрическое представление логических функций
Функцию 4-х переменных представляют в виде 4-мерного куба.

Слайд 9

Практически все булевы функции малых арностей (0, 1, 2 и

3) сложились исторически и имеют конкретные имена: Нульарные функции: При n = 0 количество булевых функций сводится к двум 220 = 21 = 2, первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами — тождественный нуль и тождественная единица. Унарные функции: При n = 1 число булевых функций равно 221 = 22 = 4. Бинарные функции: При n = 2 число булевых функций равно 22² = 24 = 16. Тернарные функции: При n = 3 число булевых функций равно 22³ = 28 = 256.

Слайд 10

Таблица значений булевых функций от одной переменной:

Слайд 11

Названия булевых функций от одной переменной:

Слайд 12

Легко, не правда ли? Даже человек, который первый раз видит материал,

составит таблицу за минуту, как максимум. А если переменных будет не 2, а 5, 10, 19? Или функция будет сложнее? Сколько времени потребуется тогда? А если человек запутается, сделает вычислительную ошибку (от которой на 100% застрахована ЭВМ)? Тогда вычисление значения функции будет, как минимум, сильно затруднено. Здесь мы подошли к самому главному. Как раз для тех случаев, где возможно исключить рутинные расчеты, можно привести программу на языке JavaScript, которая возьмет роль счетовода на себя. И будет делать это в миллионы раз быстрее (и точнее), чем человек.

Слайд 13

Ниже представлен скриншот программы, рассчитавшей таблицу значений для отрицания дизъюнкции
Т.е. от

пользователя требуется только ввести количество переменных и функцию. Остальное сделает программа. Программа может работать абсолютно с любым количеством переменных (n, где n принадлежит N). Ее возможности ограничены только возможностями компьютера, где она запущена.

Слайд 14

Чуть выше мы рассмотрели само понятие булевой функции от n переменных.

А сколько всего может быть функций n-переменных? Очевидно, что каждую функцию алгебры логики можно задать с помощью таблицы истинности, которая будет содержать 2n строк. Таким образом, функция n переменных полностью определяется набором значений из нулей и единиц длины 2n . Общее же число наборов, состоящих из нулей и единиц, длины 2n равно 22n. Значит, число различных функций алгебры логики n переменных равно 22n.
Вторая программа как раз и составляет по известному n всевозможные значения функций. Как вы понимаете, для человека этот процесс будет очень трудоемок. Но было бы неплохо иметь не только таблицу значений всевозможных функций, но и их формулы. Тут мы плавно подходим к такому понятию, как СДНФ.
Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Слайд 15

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

Содержание

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

ДЖОРДЖ БУЛЬ (1815 – 1864) Создателем алгебры логики является живший

Булевой алгебройАлгеброй Буля называется непустое множество A с двумя бинарными

Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n

Геометрическое представление логических функцийФункцию 2-х переменных можно представить на плоскости в

Геометрическое представление логических функцийФункцию 3-х переменных можно представить в 3-мерном пространстве

Геометрическое представление логических функцийФункцию 4-х переменных представляют в виде 4-мерного куба.