Совершенная дизъюнктивная нормальная форма
Логические выражения и операции
Алгебра – это наука об общих операциях, аналогичных сложению и умножению, которые выполняются не только над числами, но и над другими математическими объектами, в том числе и над высказываниями. Такая алгебра называется алгеброй логики. Алгебра логики отвлекается от смысловой содержательности высказываний и принимает во внимание только истинность или ложность высказывания.
Можно определить понятия логической переменной, логической функции и логической операции.
Логическая переменная – это простое высказывание, содержащее только одну мысль. Её символическое обозначение – латинская буква (например, A,B,X,Y и т. д). значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (0 и 1).
Составное высказывание – логическая функция, которая содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Ее символическое обозначение – F(A,B,…).
На основании простых высказываний могут быть построены составные высказывания.
Логические операции – логические действия.
Рассмотрим три базовые логические операции – конъюнкцию, дизъюнкцию, и отрицание и дополнительные – импликацию и эквивалентность.
По ходу изложения материала заполним следующую таблицу:
| Конъюнкция (от лат.conjunctio- связываю)
| Дизъюнкция (от лат. disjunctio –различаю)
| Инверсия (от лат. inversio- переворачиваю)
| Импликация (от лат. implicatio – тесно связывать)
| Эквивалентность (от лат. aequivalens – равноценное)
| Название
| Логическое умножение
| Логическое сложение
| Отрицание
| Логическое следование
| Логическое равенство
| Обозначение
| А&В или А^В
| Аv В
| А или
Ā
| А→В
А – условие
В - следствие
| А≡В или А↔В
| Союз в естественном языке
| А и В
| А или В
| Не А
| Если А, то В; когда А, тогда В; коль скоро А то В
| А тогда и только тогда, когда В
| Примеры
А – «Число 10 –четное»; В- «Число 10 – отрицательное»
| «Число 10 –четное и отрицательное» = ЛОЖЬ
| «Число 10 –четное или отрицательное» =ИСТИНА
| «Неверно, что число 10 – четное»= ЛОЖЬ; «Неверно, что число 10 отрицательное» = ИСТИНА
| «Если число 10 - четное, то оно является отрицательным»=ЛОЖЬ,
| «Число 10 – четное тогда и только тогда, когда отрицательно» =ЛОЖЬ
| Таблица истинности - таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываний
|
|
|
|
|
| Вывод: результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны
| Вывод: результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным в остальных случаях
| Вывод: результат будет ложным, если исходное выражение истинно, и наоборот
| Вывод: результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В)
| Вывод: результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны
| Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно:
1) действия в скобках;
2) инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность
Пример 4.
Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку».
- Проанализируем составное высказывание.
оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку», обозначим их через логические переменные:
А= Петя поедет в деревню;
В = Будет хорошая погода;
С = Он пойдет на рыбалку.
- Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки:
F=A& (B→C).
III. Закрепление изученного материала
Упражнение 2
Есть два простых высказывания:
А - «Число 10 – четное»;
В - «Волк травоядное животное».
Составьте из них все возможные составные высказывания и определите их истинность. Ответ:
А&В
| А v В
| А
| В
| А→В
| А↔В
| ЛОЖЬ (0)
| ИСТИНА (1)
| ЛОЖЬ (0)
| ИСТИНА (1)
| ЛОЖЬ (0)
| ЛОЖЬ (0)
|
Упражнение 3
Запишите следующие высказывания в виде логических выражений.
- Число 13 нечетное и двузначное.
- Неверно, что корова хищное высказывание.
- На уроке информатики ученики выполняли практическую работу и сообщали результаты учителю.
- Если число делится на 2, то оно четное
- Если Маша сестра Саши, то Саша – брат Маши.
- Водительские права можно получать тогда и только тогда, когда тебе исполнится 18 лет.
- Компьютер выполняет вычисления, если он включен.
Упражнение 4
Даны высказывания: А - «р делится на 5» и В- «р - нечетное число». Найти множество значений р при которых результат а) логического сложения и б) логического умножения будет:
1) истинным;
2) ложным.
Упражнение 5
Составьте и запишите истинные сложные высказывания из простых с использованием логических операций.
- Неверно, что 10>Y>5 и Z<0. Ответ: ((Y<10) &(Y>5)&(Z<0)).
- А является max(A,B,C). Ответ: (A>B) & (A>C).
- Все числа X,Y,Z равны 12. Ответ: (X=12) & (Y=12) & (Z=12).
- Любое из чисел X,Y, Z отрицательно. Ответ: (X<0) v (Y<0)v(Z<0).
Упражнение 6
Найдите значение логических выражений:
1) F=(0v0)v(1v1) (ответ: 1)
2) F=(1v1)v(1v0) (ответ: 1)
3) F=(0&0)&(1&1) (ответ: 0)
4) F= 1&(1v1)v(0&1) (ответ: 1)
IV. Итоги урока
Оценить работу класса и назвать учащихся, отличившихся на уроке.
Домашнее задание
Уровень знания: выучить основные определения, знать обозначения.
Уровень понимания:
Задача 1
Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ». Запишите логические высказывания с помощью логических операций и определите их истинность.
- Андрей старше Светы. Наташа старше Светы.
- Один десятый класс идет на экскурсию в музей. Второй десятый класс идет в театр.
- На полке стоят учебники. На полке стоят справочники.
- Часть детей – девочки. Остальные – мальчики.
Задача 2
Для логических выражений сформулируйте составные высказывания на обычном языке:
1) (Y>1и Y<3) или (Y<8 и Y>4)
2) (X=Y) и(X=Z)
3) Не (X<0) или (X<B)
4) (X>A) или (X>B)
Уровень применения: приведите примеры составных высказываний из приведенных ниже школьных предметов и запишите их с помощью логических операций:
1) биология
2) география
3) алгебра
4) информатика
5) литература
6) геометрия
7)русский язык
Урок 2. Таблицы истинности.
Цели: сформировать навыки построения таблиц истинности; сформировать у учащихся представление об устройствах элементной базы компьютера; сформировать навыки построения логических схем.
III. Изложение нового материала
Таблицы истинности
Решение логических выражений принято записывать в виде таблиц истинности - таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.
Для составления таблицы необходимо:
1. Выяснить количество строк в таблице (вычисляется как 2n, где n - количество переменных).
2. Выяснить количество столбцов = количество переменных + количество логических операций.
3. Установить последовательность выполнения логических операций.
4. Построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных.
5. Заполнить таблицу истинности по столбцам. Пример 1
Построим таблицу истинности для выражения F = (AvB)&(AvB).
Количество строк = 22 (2 переменных) + 1 (заголовки столбцов) = 5.
Количество столбцов = 2 логические переменные (А, В) + 5 логических операций (v, &, , v,) = 7.
Расставим порядок выполнения операций:
1 5 2 4 3
(A v B) & (`A v`B)
Построим таблицу:
А
| В
| A v B
| `А
| `В
| `Av`B
| (A v B) & (`A v`B)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример 2
Построим таблицу истинности для логического выражения X v Y& Z
1. Количество строк = 23+1 = 9.
2. Количество столбцов = 3 логические переменные + 3 логических операций = 6.
3. Укажем порядок действий:
3 2 1
X v Y&Z
4. Нарисуем и заполним таблицу:
Основные законы логики : А = А – закон тождества
А & = 0 – закон непротиворечия
A Ú = 1 – закон исключенного третьего
= А – закон двойного отрицания
------------------------------------------------------------------------------------------------------------------------------------------------------
Свойства констант: = 1 = 0
А Ú 0 = А А & 0 = 0
А Ú 1 = 1 А & 1 = 1
------------------------------------------------------------------------------------------------------------------------------------------------------
Законы идемпотентности: А Ú А = А
А & А = A
------------------------------------------------------------------------------------------------------------------------------------------------------
Законы коммутативности: А Ú В = В Ú А
А & В = В & А
------------------------------------------------------------------------------------------------------------------------------------------------------
Законы ассоциативности: А Ú (В Ú С) = (АÚ В) Ú С
А & (В & С) = (А & В) & С
------------------------------------------------------------------------------------------------------------------------------------------------------
Законы дистрибутивности: А Ú (В & С) = (АÚ В) & (А Ú С)
А & (В Ú С) = (А & В) Ú (А& С)
------------------------------------------------------------------------------------------------------------------------------------------------------
Законы поглощения: А Ú (А & В) = А
А & (А Ú В) = А
------------------------------------------------------------------------------------------------------------------------------------------------------
Законы де Моргана:
------------------------------------------------------------------------------------------------------------------------------------------------------
Совершенная дизъюнктивная нормальная форма
Как уже указывалось, логическая функция n-переменных f(x1, x2, ..., xn) может быть задана таблицей истинности, в которой значение функции fi принимает значение 0 или 1.
СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице истинности f ; каждому единичному набору (x1, x2, ..., xn) соответствует конъюнкция всех переменных, в которой xi взято с отрицанием, если xi = 0, и без отрицания, если xi = l. Таким образом, существует взаимнооднозначное соответствие между таблицей функции f(x1, x2, ..., xn) и ее СДНФ, и, следовательно, СДНФ для всякой логической функции единственна (точнее, единственна с точностью до порядка букв и конъюнкций: это означает, что ввиду коммутативности дизъюнкции и конъюнкции, формулы, получаемые перестановкой конъюнкций и букв в конъюнкции, не различаются и считаются одной и той же СДНФ).
В совершенной дизъюнктивной нормальной форме логическая функция выражается через три функции: конъюнкцию (логическое умножение), дизъюнкцию (логическое сложение) и инверсию (отрицание). Формулы, содержащие кроме переменных (и, разумеется, скобок) только знаки функций дизъюнкции, конъюнкции и отрицания, называют булевыми
Таким образом, для того чтобы записать совершенную дизъюнктивную нормальную форму логической функции, необходимо выбрать те наборы аргументов, на которых логическая функция принимает значение 1. Представить каждый такой набор в виде произведения всех переменных, заменив в наборах значения 1 на значение соответствующей переменной, а значение 0 – на инверсное (отрицание), и соединить эти логические произведения переменных знаками дизъюнкции. Это правило еще называют правилом записи логической функции по единицам.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|