Содержание

Слайд 2

Область определения булевой функции конечна ->
можно задать значения во всех точках

Область определения булевой функции конечна -> можно задать значения во всех точках (таблица истинности)
(таблица истинности)

Слайд 3

Наиболее важные функции
Отрицание
Конъюнкция
Дизъюнкция
Импликация
Эквиваленция (или эквивалентность)

Наиболее важные функции Отрицание Конъюнкция Дизъюнкция Импликация Эквиваленция (или эквивалентность)

Слайд 4

Отрицание

Отрицание

Слайд 5

Конъюнкция

Конъюнкция

Слайд 6

Дизъюнкция

Дизъюнкция

Слайд 7

Импликация

Импликация

Слайд 8

Эквиваленция

Эквиваленция

Слайд 9

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

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

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

Слайд 10

Задание булевой функции вектором значений
f(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),..., f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1)

Задание булевой функции вектором значений f(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),..., f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1) φf=00010111

φf=00010111

Слайд 11

Задание булевой функции номером
Каждой функции присваивается порядковый номер в виде натурального числа,

Задание булевой функции номером Каждой функции присваивается порядковый номер в виде натурального
двоичный код которого представляет собой столбец значений функции в таблице истинности.

Слайд 12

Пример

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

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

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

Слайд 13

Пример

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

0

0

0

0

1

1

1

1

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

Слайд 14

Формулами

Формулами

Слайд 15

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

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

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

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

Слайд 16

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых
эта формула принимает значение 1 (0).
Формула называется тождественно-истинной, или тавтологией (тождественно-ложной или противоречием), если эта формула принимает значение 1 (0) при всех наборах значений переменных.

Слайд 17

Пусть А и В – две формулы, зависящие от одного и того

Пусть А и В – две формулы, зависящие от одного и того
же списка переменных. Будем называть их равносильными, если для любого набора значений переменных они принимают одинаковые значения

Слайд 18

свойства логических операций

свойства логических операций

Слайд 21

Любая из равносильностей легко может быть доказана с помощью таблицы истинности

Любая из равносильностей легко может быть доказана с помощью таблицы истинности

Слайд 23

Однако часто равносильность экономнее доказывать без составления полной таблицы истинности, а с

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

Слайд 26

Нормальные формы
Элементарной конъюнкцией называется конъюнкция, составленная из попарно различных переменных или

Нормальные формы Элементарной конъюнкцией называется конъюнкция, составленная из попарно различных переменных или
отрицаний переменных.
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция попарно различных элементарных конъюнкций.

Слайд 27

Элементарной дизъюнкцией называется дизъюнкция, составленная из попарно различных переменных или отрицаний переменных.

Элементарной дизъюнкцией называется дизъюнкция, составленная из попарно различных переменных или отрицаний переменных.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция попарно различных элементарных дизъюнкций.

Слайд 28

Совершенные нормальные формы
Cовершенной ДНФ называется ДНФ, в которой
- нет одинаковых элементарных конъюнкций

Совершенные нормальные формы Cовершенной ДНФ называется ДНФ, в которой - нет одинаковых
и
все конъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз ( возможно с отрицанием) X&Y&¬Z V X&Y& Z

по всем наборам с=(с1, с2, …, сn) из 0 и 1

Слайд 29

Совершенные нормальные формы
Cовершенной КНФ называется КНФ, в которой
- нет одинаковых элементарных дизъюнкций

Совершенные нормальные формы Cовершенной КНФ называется КНФ, в которой - нет одинаковых
и
- все дизъюнкции состоят из одного и того же набора переменных, в который каждая переменная входит только один раз  ( возможно с отрицанием) (¬ X VY V Z) & (X V¬Y V Z).

по всем наборам с=(с1, с2, …, сn) из 0 и 1

Слайд 30

Алгоритм получения СДНФ по таблице истинности
Отметить те строки ТИ, в последнем

Алгоритм получения СДНФ по таблице истинности Отметить те строки ТИ, в последнем
столбце которых стоят 1:
Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: - если значение некоторой переменной в данной строке =1, то в конъюнкцию включают саму эту переменную,
- если =0, то ее отрицание:
Все полученные конъюнкции связать в дизъюнкцию:

Слайд 31

Алгоритм получения СДНФ по таблице истинности

Алгоритм получения СДНФ по таблице истинности

Слайд 32

Алгоритм получения СКНФ по таблице истинности
Отметить те строки ТИ, в последнем столбце

Алгоритм получения СКНФ по таблице истинности Отметить те строки ТИ, в последнем
которых стоят 0:
Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: - если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную,
- если =1, то ее отрицание:
Все полученные дизъюнкции связать в конъюнкцию:

Слайд 33

Алгоритм получения СКНФ по таблице истинности

Алгоритм получения СКНФ по таблице истинности
Имя файла: 1.pptx
Количество просмотров: 49
Количество скачиваний: 0