Сделай Сам Свою Работу на 5

Совершенная дизъюнктивная нормальная форма





Логические выражения и операции

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

Можно определить понятия логической переменной, логической функции и логической операции.

Логическая переменная – это простое высказывание, содержащее только одну мысль. Её символическое обозначение – латинская буква (например, A,B,X,Y и т. д). значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (0 и 1).

Составное высказывание – логическая функция, которая содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Ее символическое обозначение – F(A,B,…).

На основании простых высказываний могут быть построены составные высказывания.

Логические операции – логические действия.

Рассмотрим три базовые логические операции – конъюнкцию, дизъюнкцию, и отрицание и дополнительные – импликацию и эквивалентность.



По ходу изложения материала заполним следующую таблицу:

  Конъюнкция (от лат.conjunctio- связываю) Дизъюнкция (от лат. disjunctio –различаю) Инверсия (от лат. inversio- переворачиваю) Импликация (от лат. implicatio – тесно связывать) Эквивалентность (от лат. aequivalens – равноценное)
Название Логическое умножение Логическое сложение Отрицание Логическое следование Логическое равенство
Обозначение А&В или А^В Аv В ­­ А или Ā ­ А→В А – условие В - следствие А≡В или А↔В
Союз в естественном языке А и В А или В Не А Если А, то В; когда А, тогда В; коль скоро А то В А тогда и только тогда, когда В
Примеры А – «Число 10 –четное»; В- «Число 10 – отрицательное» «Число 10 –четное и отрицательное» = ЛОЖЬ «Число 10 –четное или отрицательное» =ИСТИНА «Неверно, что число 10 – четное»= ЛОЖЬ; «Неверно, что число 10 отрицательное» = ИСТИНА «Если число 10 - четное, то оно является отрицательным»=ЛОЖЬ, «Число 10 – четное тогда и только тогда, когда отрицательно» =ЛОЖЬ
Таблица истинности - таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываний
А В А&В

 



А В АvВ

 

А А

 

А В А→В

 

А В А≡В

 

Вывод: результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны Вывод: результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным в остальных случаях Вывод: результат будет ложным, если исходное выражение истинно, и наоборот Вывод: результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В) Вывод: результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно:

1) действия в скобках;

2) инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность

Пример 4.

Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку».



  1. Проанализируем составное высказывание.

оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдет на рыбалку», обозначим их через логические переменные:

А= Петя поедет в деревню;

В = Будет хорошая погода;

С = Он пойдет на рыбалку.

  1. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки:

F=A& (B→C).

 

III. Закрепление изученного материала

Упражнение 2

Есть два простых высказывания:

А - «Число 10 – четное»;

В - «Волк травоядное животное».

Составьте из них все возможные составные высказывания и определите их истинность. Ответ:

А&В А v В А В А→В А↔В
ЛОЖЬ (0) ИСТИНА (1) ЛОЖЬ (0) ИСТИНА (1) ЛОЖЬ (0) ЛОЖЬ (0)

 

Упражнение 3

Запишите следующие высказывания в виде логических выражений.

  1. Число 13 нечетное и двузначное.
  2. Неверно, что корова хищное высказывание.
  3. На уроке информатики ученики выполняли практическую работу и сообщали результаты учителю.
  4. Если число делится на 2, то оно четное
  5. Если Маша сестра Саши, то Саша – брат Маши.
  6. Водительские права можно получать тогда и только тогда, когда тебе исполнится 18 лет.
  7. Компьютер выполняет вычисления, если он включен.

Упражнение 4

Даны высказывания: А - «р делится на 5» и В- «р - нечетное число». Найти множество значений р при которых результат а) логического сложения и б) логического умножения будет:

1) истинным;

2) ложным.

Упражнение 5

Составьте и запишите истинные сложные высказывания из простых с использованием логических операций.

  1. Неверно, что 10>Y>5 и Z<0. Ответ: ((Y<10) &(Y>5)&(Z<0)).
  2. А является max(A,B,C). Ответ: (A>B) & (A>C).
  3. Все числа X,Y,Z равны 12. Ответ: (X=12) & (Y=12) & (Z=12).
  4. Любое из чисел 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

Из двух простых высказываний постройте сложное высказывание, используя логические связки «И», «ИЛИ». Запишите логические высказывания с помощью логических операций и определите их истинность.

  1. Андрей старше Светы. Наташа старше Светы.
  2. Один десятый класс идет на экскурсию в музей. Второй десятый класс идет в театр.
  3. На полке стоят учебники. На полке стоят справочники.
  4. Часть детей – девочки. Остальные – мальчики.

Задача 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. Нарисуем и заполним таблицу:

X Y Z `Z Y&`Z X v Y&`Z

 

Основные законы логики : А = А – закон тождества

А & = 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 Все материалы защищены законодательством РФ.