содержание 1определение 1.определение 2.логическоеотрицание 2.логическое отрицание 3.логическое сложение 4.логическое умножение 5логическоеследование 5.логическое следование 6.эквивалентность 7.законы алгебры логики 8логическиевысказывания 8.логические высказывания 9.типызадач 9.типы задач а).составление таблиц истинности бупрощениевыражений б).упрощение выражений б).решение логических задач 10ДНФи КНФ 10.ДНФ и КНФ 12.контрольная работа 11.СДНФ и СКНФ а).составление таблиц истинности выход

Основные понятия алгебры логики Алгебра логики изучает логические функции Логическая функция Алгебра логики изучает логические функции. Функция - это закон соответствия между переменными.Логическая функция - это закон соответствия между логическими переменными. Логическая переменная Логическая переменная - это такая переменная, относительно которой можно утверждать,что она истинна или она ложна. Если факт истинности обозначать 1, а лжи 0, то можно считать, что логическая перемененная принимает два значения 1 или 0. Логические функции и переменные определены на множестве двух значений {0,1}

Пусть есть высказывание: А А= я сегодня пойду в школу Логическое отрицание Логическое отрицание Это логическая функция, которая принимает ложное значение при истинном значении переменной и истинное значение пи ложном Высказывание: Ане логическим А =я сегодня не пойду в школу является логическим отрицаниемА отрицанием для высказывания А Высказывание: АА АА =я сегодня не пойду в школу является логическим отрицанием отрицанием для высказывания А Таблица истинности А не Элемент не

Пусть есть два высказывания: А А= я сегодня пойду в школу ВВ ВВ = я сегодня пойду гулять Логическое сложение - дизъюнкция Это логическая функция, которая принимает ложное значение при ложном значении всех входящих в нее переменных Высказывание Высказывание: А + В А + В =я сегодня пойду в школу или я сегодня пойду гулять логическим сложением является логическим сложением этих двух высказываний Высказывание Высказывание: А + ВВ ВВ =я сегодня пойду в школу или я сегодня пойду гулять является логическим сложением сложением этих двух высказываний Таблица истинности В А + В V А или Элемент или

Пусть есть два высказывания: А А= я сегодня пойду в школу В = я сегодня пойду гулять Логическое умножение - конъюнкция Логическое умножение - конъюнкция Это логическая функция, которая принимает истинное значение при истинном значении всех входящих в нее переменных Высказывание: А * ВВ ВВ =я сегодня пойду в школу ии ии я сегодня пойду гулять является логическим умножением умножением этих двух высказываний Таблица истинности А В А*В И Элемент И

Пусть есть два высказывания: А А= я сегодня пойду в школу ВВ ВВ = я сегодня пойду гулять Логическое следование- импликация Это логическая функция, которая принимает ложное значение, если первое высказывание ложно, а второе истинно Высказывание: А ВВ ВВ = если если я сегодня пойду в школу, то то я сегодня пойду гулять является логическим следованием Таблица истинности В А B А следование Элемент - следование

Пусть есть два высказывания: А А= я сегодня пойду в школу ВВ ВВ = я сегодня пойду гулять Равнозначность-эквивалентность Это логическая функция, которая принимает истинное значение, при одинаковых значениях переменных. Высказывание: А ВВ ВВ = для того чтобы я сегодня пошла в школу, необходимо и достаточно достаточно,чтобы я сегодня пошла гулять является эквивалентностью Таблица истинности В А В эквивалентность Элемент -эквивалентность А

Законы алгебры логики А+ 0 = А А * 0 = 0 А + 1 = 1 А * 1 = А А+ А = А А * А = А А + А = 1 А * А = 0 Дистрибутивный закон А*(В + С) = А*В+ А*С А+(В*С)=(А+В)*(А+С) Коммутативный закон А + В = В + А А* В = В* А А = А Закон поглощения А*(А+В)=А А+А*В=А правило свертки А*В+А*В=В (А+В)*(А+В)=В Закон склеивания А+А*В=А + В Правило Де Моргана А*В =А + В А+В =А * В А B = +BА B = *B+ *B

Логические высказывания

Типовые задачи по преобразованию логических функций Все задачи можно разделить на следующие типовые группы: 1.Упрощение логических функций 2.Построение таблицы истинности функции 3.Определение тождественности логических функций 4.Вычисление значения логического выражения для заданного набора значений переменных 5.построение функциональной схемы узла, реализующего заданную логическую функцию.

ДНФ и КНФ Элементарной называется конъюнкция, в которую входят только переменные и их отрицания.Например Х 1 Х 2 ; Х 1 Х 2 Х 3 ;Х 1 Х 2 Х 3 Элементарной называется дизъюнкция, представляющая собой логическую сумму переменных и их отрицаний.Например Х 1 +Х 2 ; Х 1 +Х 2 +Х 3 ; Х 1 +Х 1 +Х 3 (Д Н Ф Дизъюнктивная нормальная форма (Д Н Ф) - это форма, в которой логическая функция представляется в виде дизъюнкции элементарных конъюнкций. Например: F=x 1 x 2 +x 1 x 3 + x 1 x 2 x 3 (К Н Ф) Конъюнктивная нормальная форма (К Н Ф) - это форма, в которой логическая функция представляется в виде конъюнкции элементарных дизъюнкций. Например: F=(x 1 +x 2 ) *(x 1 + x 3 )* (x 1 +x 2 +x 3 )

СДНФ и СКНФ Использование нормальных форм не устраняет неоднозначность записи логических функций X 1 X 2 +X 1 X 3 +X 1 X 2 X 3 Например F=X 1 X 2 +X 1 X 3 +X 1 X 2 X 3 может быть записана: 1)F = X 1 X 2 +X 1 X 3 +X 2 X 3 2)F= X 1 X 2 +X 1 X 3 (проверьте, составляя таблицы истинности.) Поэтому среди нормальных форм выделяют такие,в которых функции записываются единственным образом. Их называют совершенными формами. СДНФ иСКНФ Применяются совершенная дизъюнктивная и совершенная конъюнктивная формы(СДНФ иСКНФ) СДНФ иСКНФ Формы СДНФ иСКНФ имеют две отличительные особенности: 1)все элементарные конъюнкции и дизъюнкции имеют одинаковый ранг 2)в элементарные конъюнкции(дизъюнкции)входят все те переменные и их отрицания, от которых зависит функция

Примеры СДНФ и СКНФ СДНФ F = X 1 X 2 X 3 +X 1 X 2 X 3 + X 1 X 2 X 3 +Х 1 Х 2 Х 3 - СДНФ СКНФ F = (X 1 +X 2 +X 3 ) *(X 1 +X 2 +X 3 ) *( X 1 +X 2 +X 3 ) *(Х 1 +Х 2 +Х 3 ) - СКНФ СДНФ F = X 1 X 2 +X 1 X 2 + X 1 X 2 - СДНФ СКНФ F = (X 1 +X 2 ) *(X 1 +X 2 ) - СКНФ F = (X 1 +X 2 ) *X 1 - не СКНФ т к второй множитель не содержит Х 2 F = (X 1 +X 3 ) *(X 1 +X 2 +X 3 ) *( X 1 +X 2 ) *(Х 1 +Х 2 +Х 3 ) -не СКНФ, т к первый и третий множитель не содержат Х 2 и Х 3 соответственно F = X 1 X 2 +X 2 + X 1 X 2 - не СДНФ,т к второе слагаемое не содержит Х 1

СДНФ Правило записи СДНФ функции по таблице истинности: Для всех наборов переменных, на которых функция принимает единичные значения,записать конъюнкции, инвертируя те переменные,которым соответствуют нулевые значения. Затем конъюнкции соединить знаками дизъюнкции. СДНФ Функции в СДНФ обычно записывают по таблицам истинности следующим образом: Пример : Для наборов 3,5,6,7 записываем конъюнкции Х 1 Х 2 Х 3, Х 1 Х 2 Х 3, Х 1 Х 2 Х 3 соединяем их знаком дизъюнкции Получаем: СДНФ: F = Х 1 Х 2 Х 3,+ Х 1 Х 2 Х 3 + Х 1 Х 2 Х 3

CКНФ Правило записи CКНФ функции по таблице истинности: Для всех наборов переменных, на которых функция принимает нулевые значения,записать дизъюнкции, инвертируя те переменные,которым соответствуют единичные значения. Затем дизъюнкции соединить знаками конъюнкций. СКНФ Функции в СКНФ обычно записывают по таблицам истинности следующим образом: Пример : Для наборов 1,3,5,6 записываем дизъюнкции Х 1 +Х 2 +Х 3, Х 1 +Х 2 +Х 3, Х 1 +Х 2 +Х 3, Х 1 +Х 2 +Х 3 соединяем их знаком конъюнкции Получаем: ) F = (Х 1 +Х 2 +Х 3 )* ( Х 1 +Х 2 +Х 3 )* (Х 1 +Х 2 +Х 3 )* ( Х 1 +Х 2 +Х 3 ) СКНФ:

Упрощение выражений 1.Упростить F =(A+B+C)(A+B+C) Решение: F=(А+В+C)(А*В*C)=А*А*В*С+В*А*В*С+С*А*В*С= В 0 =А*В*С 2.Упростить: F=((A*B C) (A*C)) B Решение: 1)А*В C =A*B +C=A+B+C 2)(A+B+C ) (A*C)= (A+B+C )* (A*C)+ (A+B+C )* (A*C) 2)(A+B+C ) (A*C)= (A+B+C )* (A*C)+ (A+B+C )* (A*C)= =A*A*C+B*A*C+C*A*C+(A*B*C)(A+C)=B*A*C+A*B*C*A+A*B*C*C =B*A*C )B*A*C B=B*A*C+B=B+A+C+B=1+A+C=1 1

Решение задач Экзамен сдавали четыре абитуриента А,В,С,D. Известно 1)Для того, чтобы А не сдал или В сдал, необходимо, чтобы С сдал и D не сдал. 2)Для того, чтобы не сдал С, а В сдал, необходимо, чтобы А не сдал или D сдал экзамен. 3)Неверно, что для того, чтобы не сдал А, достаточно, чтобы сдал D Кто сдал экзамен? Задача 1 Запишем каждое высказывание в виде логических функций: 1)F 1 =(A+B) (C*D)2)F 2 =C*B (A+D)3)F 3 =D A F 1 *F 2 *F 3 истина 1) F 1 =(A+B) (C*D) =(A+B)+ (C*D) =A*B+C*D 2) F 2 =C*B+A+D=C+B+A+D 3) F 3 =D A=D+A3) F 3 =D A=D+A= D*A 4)F 1 * F 2 =(A*B+C*D)*(C+B+A+D)=ABC+ABB+ABA+ABD+CDC+CDB+CDA+CDD= = =ABC+AB+ABD+CD+CDB+CDA=AB+CD ABD 5 ) F 1 * F 2 *F3=(AB+CD)*D*A=ABDA+CDDA=ABD Ответ: А сдал В не сдал D сдал

Задача 2 Четыре студентки Мария, Нина, Ольга и Полина участвовали в соревнованиях по плаванью и заняли четыре первые места.На вопрос о распределению мест последовало три разных ответа: 1) Ольга первая, Нина вторая 2)Ольга вторая, Полина третья 3) Марина вторая, Полина четвертая В каждом ответе по крайней мере одна часть верна.Определите распределение мест.Решение Запишем каждое высказывание в виде логических функций: 1)F 1 =О1+Н2 2)F 2 =О2+П32)F 3 =М2+П4 F= (О1+Н2)*(О2+П3)*(М2+П4)=(О1*О2+О1*П3+Н2*О2+Н2*П3)*(М2+П4) F =(О1*П3+Н2*П3)*(М2+П4)=О1*П3*М2+О1*П3*П4+Н2*П3*М2+Н2*П3*П4 F=О1*П3*М Ответ:Ольга 1место Полина 3 место Марина 2 место F 1 *F 2 *F 3 истина

Задача 3 На вопрос, кто из школьников изучал логику был получен правильный ответ: Если изучал первый, то изучал и третий Неверно, что если изучал второй, то изучал третий Определите, кто изучал логикуРешение Запишем каждое высказывание в виде логических функций: 1)F 1 =первый третий F 2 =второй F=F 1 *F 2 истина F= (первый третий)*( второй третий)=(первый + третий)*( второй +третий)= = (первый + третий)*( второй * третий)=первый * второй * третий + третий * второй* третий = первый* второй* третий 1 трети й 0 Ответ: второй

Контрольная работа