Учебное пособие Алгебра логики

0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 0 Ответ: А - ,   Б - Уровень Б:  1).                               2). X Y Z F X Y Z F 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 Ответ: 1). - ,   2). - Уровень В:  a b c 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 Ответ: 4. Является ли высказывание (X®Y)«(Y®X) тавтологией. Выписать СКНФ и СДНФ. 5. Установить эквивалентны ли высказывания. Выписать СКНФ или СДНФ. а)                    б)                         . 6. Напишите полином Жегалкина для формул.   а);   б)   7.Является ли функция  самодвойственной?   8. Определите монотонность данных функций. а)                     б)                               Рекомендуемая литература.   1.Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-пресс, 2007. – 176с. 2. Гуц А. К. Математическая логика и теория алгоритмов. – Омск, Изд-во Наследие. Диалог-Сибирь, 2003. – 108 с. 3. Зюзьков В. М., Шелупанов А. А. Математическая логика и теория алгоритмов. – М.: «Горячая линия – Телеком», 2007. – 176с. 4. Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов. – М.: «Академия», 2007. – 304с. 5. Колмогоров А. Н., Драгалин А. Г. Математическая логика. – М.: «Физматлит», 2006. – 240с. 6. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: «Физматлит», 2004. – 256с. 7.Таран, Т. А. Сборник задач по дискретной математике / Т.А. Таран, Н.А. Мыценко, Е.Л. Темникова. – 2-е изд., перераб. и доп. – Киев: Инрес, 2005. – 64 с. 8. Шапорев С. Д. Математическая логика. Курс лекций и практических занятий. – С-Пб.: «БХВ-Петербург», 2005. – 416с.

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ - ТЕХНИКУМ «ШЕНТАЛИНСКОЕ МЕДИЦИНСКОЕ УЧИЛИЩЕ» Учебное пособие Дисциплина: Элементы математической логики Раздел 2: «Алгебра логики» Шентала 2013 г.

 

39

2

f4 + + – + – В соответствии с теоремой Поста набор функций будет полным тогда и только тогда, когда в каждом столбце таблицы Поста имеется хотя бы один минус. Таким образом, из приведенной таблицы следует, что данные 4 функции образуют полный набор, но эти функции не являются базисом. Из этих функций можно образовать 2 базиса: f3, f1 и f3, f2. Полными наборами будут любые наборы содержащие, какой-либо базис. Непосредственно из таблицы Поста следует, что число базисных функций не может быть больше 5. Нетрудно доказать, что на самом деле это число меньше или равно 4. Задания для самостоятельного решения. 1.Дано высказывание: “Макаров является членом сборной команды “Кодр”. Какое из следующих высказываний есть логическим отрицанием данного? а). Не Макаров является членом сборной команды “Кодр”. б). Макаров является членом сборной команды не “Кодр”. в). Макаров не является членом сборной команды “Кодр”. г). Неверно, что Макаров является членом сборной команды “Кодр”. 2. Определите значения истинности высказываний: а). “Если 16 делится на 4, то 16 делится на 2”. б). “Если 17 делится на 4, то 17 делится на 2”. в). “Если 18 делится на 4, то 18 делится на 2”. г). “Если 18 делится на 2, то 18 делится на 4”. д). “Если 2· 2=5, то 83 ¹ 500”. е). “Если 2· 2=4, то 72 =81”. ж). “Если телепатия существует, то некоторые физические законы требуют пересмотра”. 3.  По заданной таблице истинности составить логическое выражение - формулу и на ее основе построить функциональную схему.  Уровень  А:  1).                                   2). X Y F X Y F

Одобрено ЦМК «Общих гуманитарных и социально-экономических и математических и естественнонаучных дисциплин » Председатель _______М.Б. Мутыгуллина Протокол № ___ от «___»____________2013г. Составлено в соответствии с государственными требованиями к минимуму содержания и уровню подготовки выпускников  по специальности 230115 «Программирование в компьютерных системах» Зам. директора по УР ___________ Е.В.Курганская «___»____________2013г Составитель:  Панина Л.И.

 

38

3

Класс S – класс самодвойственных функций. Функция п переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, т. е. самодвойственная функция f(x1, x2,…,xn) удовлетворяет условию f (x1,x2, ..., xn ) =. Например, функции  f3, f4 - являются самодвойственными, а функции f1, f2  – не являются. Нетрудно устанавливается следующий факт. Теорема. Классы функций Т0, Т1, L, M, S замкнуты. Это утверждение следует непосредственно из определения самих этих классов, а также из определения замкнутости. В теории булевых функций очень большое значение имеет следующая теорема Поста. Теорема Поста. Для того чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T0, T1, L, M, S. Из этой теоремы следует довольно простой способ выяснения полноты некоторого набора функций. Для каждой из этих функций выясняется принадлежность к перечисленным выше классам. Результаты заносятся в так называемую таблицу Поста (в нашем примере эта таблица составлена для 4-х функций, причем знаком “+” отмечается принадлежность функции соответствующему классу, знак “–” означает, что функция в него не входит). f T0 T1 L M S f1 + – + – – f2 + – – – + f3 – + – – –

РЕЦЕНЗИЯ на учебное пособие по разделу «Алгебра логики» дисциплины «Элементы математической логики» преподавателя ГБОУ СПО ШМУ Л.И.Паниной Учебное пособие составлено в соответствии с требованиями ФГОС СПО по специальности 230115 «Программирование в компьютерных системах» для студентов 2 курса  и предназначено для аудиторной и самостоятельной подготовки студентов по дисциплине «Элементы математической логики» при изучении раздела «Алгебра логики». Учебное пособие рассмотрено и одобрено ЦМК ОГСЭ и ЕН дисциплин. Основой разработки пособия явилась Рабочая программа дисциплины. Учебное пособие состоит из содержания, рекомендаций для студентов по работе с учебным пособием, пояснительной записки, теоретического  материала по темам раздела «Алгебра логики» с примерами решения задач и упражнений, заданий для самостоятельного выполнения, списка использованных источников. Название учебного пособия соответствует его содержанию. Учебный материал изложен логично и последовательно и в доступной для студентов форме. Теоретический и методический уровень выдержан в надлежащем виде. В целом, учебное пособие подготовлено согласно Методическим рекомендациям по составлению учебно-методического пособия управляющего типа. Рецензент: методист ГБОУ СПО ШМУ _________М.В. Бурлягина

 

37

4

М – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных: s1= (х1, х2,…, хп) и s 2 = (y1, y2,…, yп). Будем говорить, что набор s 1 меньше набора s 2 . Функция от п переменных называется монотонной, если на меньшем наборе она принимает меньшее или равное значение. Пример. В нижеследующей таблице функции f1, f2 являются монотонными функциями, а функции f3, f4 – нет.  x y f1 f2 f3 f4 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 1 Естественный порядок переменных обеспечивает тот факт, что если какой-то набор меньше другого набора, то он обязательно расположен в таблице истинности выше “большего” набора. Поэтому если в таблице истинности (при естественном порядке набора переменных) вверху стоят нули, а затем единицы, то эта функция точно является монотонной. Однако возможны инверсии, т. е. единица стоит до каких-то нулей, но функция является все равно монотонной (в этом случае наборы, соответствующие “верхней” единице и “нижнему” нулю должны быть несравнимы; можно проверить, что функция, задаваемая таблицей истинности при естественном порядке набора переменных (00010101), является монотонной);

РЕКОМЕНДАЦИИ для студентов по работе с учебным пособием Уважаемые,  студенты! Это учебное пособие поможет Вам  в подготовке к теоретическим и практическим занятиям по дисциплине «Элементы математической логики» при изучении раздела «Алгебра логики». Знания, полученные при работе с данным учебным пособием, Вы можете использовать при изучении других разделов данного курса и в будущей профессиональной деятельности. Для успешной работы с учебным  пособием необходимо: - внимательно ознакомиться с  информационным материалом, который изложен по шести темам; -    ознакомиться с примерами решения задач и упражнений по каждой теме; - затем приступить к выполнению заданий для самостоятельного решения. При необходимости проконсультируйтесь с преподавателем. Желаю удачи!

 

36

5

Так как очевидно , т. е. отрицание является суперпозицией штриха Шеффера, а дизъюнкция тогда , штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией. Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции. Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций: Т0 – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т0 – это класс функций, сохраняющих 0); Т1 – это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т1 – это класс функций, сохраняющих единицу) (заметим, что число функций от п переменных принадлежащих классам Т0 и Т1 равно 22n-1); L – класс линейных функций т. е. функций, для которых полином Жегалкина содержит только первые степени переменных;

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА            Данное учебное пособие составлено в соответствии с государственным образовательным стандартом по дисциплине «Элементы математической логики» для специальности 230115 «Программирование в компьютерных системах»            Целью создания учебного пособия является необходимость систематизации учебного материала согласно требованиям рабочей программы.         Основная цель учебного пособия – организовать и повысить качество самоподготовки студентов, а также оптимизировать проведение занятий по дисциплине «Элементы математической логики».              В результате изучения учебной дисциплины в области алгебры логики студент должен: знать:  - основные принципы математической логики; - формулы алгебры высказываний; - методы минимизации алгебраических преобразований уметь: - формулировать задачи логического характера и применять средства математической логики для их решения.       Предполагается практическое осмысление тем на практических занятиях, в процессе которых студент должен закрепить и углубить теоретические знания в области алгебры логики.

 

35

6

полный набор – это множество таких функций, через которые можно выразить все остальные булевы функции. Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным). Пример 7.2. Конъюнкция, дизъюнкция и отрицание являются полным набором, но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию. Любую функцию можно представить в виде полинома Жегалкина. Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина). Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание). Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности:

Тема 1.Высказывания. Основные логические операции 1.1. Основное понятие математической логики Основным понятием математической логики является понятие «простого высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, утверждающее что-либо о чем-либо, и при этом мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».          Примеры высказываний.          1) Москва стоит на Неве.          2) Лондон — столица Англии.          3) Сокол не рыба.          4) Число 6 делится на 2 и на 3.  Высказывания 2), 3), 4) истинны, а высказывание 1) ложно.  Очевидно, предложение «Да здравствует Россия!» не является высказыванием.          Различают два вида высказываний.          Высказывание, представляющее собой одно утверждение, принято называть простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2).          Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если .... то ...», «тогда и только тогда», принято называть сложными или составными.          Так, высказывание 3) получается из простого высказывания «Сокол - рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на З», соединенных

 

34

7

СДНФ всегда равно нулю. Следовательно, СПНФ будет иметь вид: . Все переменные с отрицанием заменяем по формуле (2), затем раскрываем скобки и из полученного выражения удаляем попарно одинаковые слагаемые в соответствии с (1): . Ответ: P(F) . Тема 6.Основные классы функций алгебры логики. Пусть имеется некоторый набор K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые функции: - полученные с помощью конечного числа применения двух операций; - можно переименовать любую переменную, входящую в функцию из K; - вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию. Суперпозицию еще иначе называют сложной функцией. Пример 7.1. Если дана одна функция х|y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x|(x|y), x|(y|z) и т. д. Замыканием набора функций из K называется множество всех суперпозиций. Класс функций K называется замкнутым, если его замыкание совпадает с ним самим. Набор функций называется полным, если его замыкание совпадает со всеми логическими функциями. Иначе говоря,

союзом «и».          Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».          В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.          Элементарные высказывания обозначаются малыми буквами латинского алфавита: х, у, z, ..., а, b, с, ...; истинное значение высказывания цифрой 1, а ложное значение - цифрой 0.          Если высказывание а истинно, то будем писать а = 1, а если а ложно, то а = 0. 1.2. Логические операции над высказываниями Над высказываниями можно проводить логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Определение: Отрицанием высказывания А называется высказывание  , которое истинно, если А ложно, и ложно, если А истинно. Высказывание читается так: «не А». Таблица истинности для А 1 0 0 1 Здесь: 1 – истина, 0 – ложь. Примеры: 1. Х: треугольник АВС – остроугольный. Х: неверно, что треугольник АВС – остроугольный. Это все равно, что: Х: треугольник АВС – прямоугольный или тупоугольный

 

33

8

Заменим операцию дизъюнкции на операцию сложения по модулю два по формуле:  . При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю (при построении СДНФ по таблице истинности это очевидно ― все наборы отличаются хотя бы по отрицанию одной переменной). Следовательно, СПНФ будет иметь вид: . Ответ:  Пример 2. Составить СПНФ булевой функции, если СДНФ данной булевой функции, имеет вид: . Решение. Заменим операцию дизъюнкции на операцию сложения по модулю два по формуле:  . При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю (при построении СДНФ по таблице истинности это очевидно ― все наборы отличаются хотя бы по отрицанию одной переменной). Следовательно, СПНФ будет иметь вид: Пример 3. Составить канонический поли­ном Жегалкина P(F) булевой функции, если СДНФ данной булевой функции, имеет вид: . Решение. Заменим операцию дизъюнкции  операцией сложения по модулю два по (6). При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций

2. А: Иванова М. на экзамене по математике получила 4. : Неверно, что Иванова М. по математике получила 4.       Определение: Дизъюнкцией высказывания А и В называется высказывание АВ, истинное при условии, что хотя бы одно из высказываний А или В истинно. Его читают «А или В». Таблица истинности для АВ А В АВ 0 0 0 0 1 1 1 0 1 1 1 1 Примеры: 1. По математике будет зачет или экзамен.                   2. 10 – простое или составное число. Определение: Конъюнкцией высказываний А и В называется высказывание АВ, которое истинно лишь при условии, что истинны оба высказывания и А, и В. Высказывание А  В читается «А и В». Таблица истинности А В АВ 0 0 0 0 1 0 1 0 0 1 1 1     Примеры: 1. На этот раз ответчик явился и суд состоялся. – истина                2. В прямоугольном треугольнике сумма двух любых углов больше или равна третьего угла и гипотенуза меньше катета. – ложь

 

32

9

5.3. Примеры решения задач и упражнений. Рассмотрим на примерах построение СПНФ, используя преобразование СДНФ булевой функции и канонический полином Жегалкина. Пример 1. Составить СПНФ булевой функции, заданной вектором значений таблицы истинности w(F)=(10010010).  Решение. Так как вектор значений заданной булевой функции имеет 8=23 разрядов, следовательно, булевой функции соответствует следующая таблица истинности: F 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 СДНФ данной булевой функции, построенная  по таблице истинности будет иметь вид: .

Определение: Импликацией высказываний А и В называется высказывание АВ, ложное лишь при условии, что А истинно, а В ложно. Его читают: «Если А, то В». Таблица истинности А В АВ 0 0 1 0 1 1 1 0 0 1 1 1 Примеры: 1. Если я сдам зачет, то пойду в кино.       2. Если треугольник равнобедренный, то углы при его основании равны. Определение: Эквиваленцией высказываний А и В называется высказывание АВ, истинное в том и только в том случае, когда А и В имеют одну и ту же истинность (т.е. либо оба истинны, либо оба ложны). Читают: «А тогда и только тогда, когда В» или «А необходимо и достаточно для В» Таблица истинности А В АВ 0 0 1 0 1 0 1 0 0 1 1 1 Таблица истинности для всех логических операций:

 

31

10

(1)                                                              (2)                                                         (3)                                                          (4) ,       если                                    (5) ,                  (6) если   для   , ,  . Метод построения полинома P(F) заключается в последова­тельном выполнении следующих действий: 1) выписывается СДНФ булевой функции F; 2) на основе применения (6) СДНФ F пре­образуется в СПНФ функции F; 3) в СПНФ все переменные с отрицанием заменяют­ся по формуле (2); 4) в скобочной форме осуществляется раскрытие скобок согласно (3); 5) из полученного выражения удаляются попарно одинаковые слагаемые в соответствии с (1); 6) полу­ченное выражение обозначается через P(F).  Приведем полиномы Жегалкина элементарных булевых функций

Используя таблицы истинности логических операций, можно составить таблицы истинности сложных высказываний и определить, является ли они истинными при заданных значениях истинности исходных высказываний. Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначается Тема 2. Формулы и законы алгебры логики 2.1. Формулы логики     С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой. Логическую формулу можно определить следующим образом:

 

30

11

Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) полиномы P(F) и Q(F) имеют вид: , . Отметим некоторые свойства монотонно-поляризованных поли­номов P(F) и Q(F) булевой функции : 1. Полиномы P(F) и Q(F) являются для булевой функции F единственными. 2. Полиномы P(F) и Q(F) имеют степень n тогда и только тогда, когда     таблица истинности функции F содержит нечетное число единиц. 3. Число слагаемых полинома P(F) (Q(F)) четно тогда и только тогда, когда     (соответственно ). Основным достоинством представления булевых функций в виде  канонического поли­нома Жегалкина является то, что в этом представлении любая булева функция задается с помощью всего двух логических операций: конъюнкции и сложения по модулю два, что сокращает набор различных элементов для синтеза логи­ческих схем. Опишем метод построения канонического поли­нома Жегалкина P(F) путем преобразования СДНФ для произвольных булевых функций n  пе­ременных F, заданных посредством таблицы истинности. Предварительно отметим основные свойства логической опе­рации сложения по модулю два, которые используются при описа­нии метода. Имеет место

1.              Всякая логическая переменная (x, y, z ,..) и символы истина (1) и ложь (0) — формулы. 2.              Если F - формула, то  - также формула. 3.              Если F1 и F2 - формулы, то , , ,  - тоже формулы 4.              Никаких других формул в алгебре логики нет. Формализовать - значит: 1) Каждому простому предложению сопоставить элементарную формулу. 2) Если предложение составное, то выделяем простые предложения, заменяем их на элементарные формулы, вместо связок расставляем знаки логических операций. 3) Если нужно, расставляем круглые скобки. Пример: Рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Обозначим буквой A высказывание: "купить яблоки", буквой B - высказывание: "купить абрикосы",буквой C - высказывание: "испечь пирог". Тогда высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог"формализуется в виде формулы: (A v B)  C. Некоторые формулы принимают значение “истина” при любых значениях истинности входящих в них переменных. Такие формулы называются тождественно истинными формулами или тавтологиями. Тавтология - формула, которая истинна при любом наборе значений входящих в неё переменных (тождественно истинная формула). Например,  ,   ,

 

29

12

Число конъюнкций, образующих полином, называется длиной полинома, а максимальный ранг элементарной конъюнкции – степенью полинома.                                                                                           В приведенном выше примере длина полинома функции F равна 3, а степень – 2. Определение. Полином функции F, состоящий только из полных элементар­ных конъюнкций, называется совершенной ПНФ (СПНФ). По аналогии с СДНФ такое представление конкретной булевой функции F явля­ется единственным. Полином F, содержащий наименьшее число слагаемых среди всех полиномов, реализующих функцию F, называется кратчайшей ПНФ (КрПНФ).Полином функции F, содержащий наименьшее число вхождений литералов, называется минимальной ПНФ. 5.2. Разложение булевых функций в канонический полином Жегалкина Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логи­ческих схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА. Определение. Полином булевой функции F, в слагаемые которого все переменные F входят только без отрица­ния или только с отрицанием, называется монотонно-поляризован­ным. Причем в первом случае полином функции F называется поло­жительно-поляризованный и обозначается черезP(F), а во втором случае - отрицательно-поляризованным и обозначается через Q(F). Полином P(F) иначе называется каноническим полиномом Жегалкина (или в зарубежной научно-технической литературе - формой Рида-Мюллера).

 

Некоторые формулы принимают значение “ложно” при любых значениях истинности входящих в них переменных. Такие формулы называются тождественно ложными формулами или противоречиями.   Тождественно ложная формула - формула, которая ложна при любом наборе значений входящих в неё переменных (противоречие). Например,  . Если в формулу входит n переменных, то формула будет иметь 2n наборов значений. При составлении таблиц истинности для данных формул сначала определяем все возможные наборы переменных, входящих в формулу. Затем определяем истинность каждого члена этой формулы. А далее уже и определяем истинность самой формулы для каждого набора. Логические операции имеют следующий приоритет: действия в скобках, инверсия , ,, . Пример: Определение. Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний (переменных).

28

13

Функция "И" равна единице, если равны единице ВСЕ ее аргументы. Функция "ИЛИ" равна единице, если равен единице ХОТЯ БЫ один аргумент. Функция "ИСКЛЮЧАЮЩЕЕ ИЛИ" (сумма по модулю 2) равна единице, если равен единице ТОЛЬКО один ее аргумент. Тема 5. Многочлен Жегалкина. 5.1. Полиномиальное разложение булевых функций Определение.  Под полиномом булевой функции F понимается представление F  посредством сложения по модулю два попарно различных элементарных конъюнкций. Иначе такое представление F называется полиномиальным разложением или полиномиальной нормальной формой (ПНФ) функции F. Например, полиномом булевой функции F, заданной вектором значений таблицы истинности w(F)=(00100111),  является следующее выражение .

Обозначение. A≡B.      Пример. . 2.2. Законы алгебры логики  Основные, наиболее часто встречающиеся равносильности, называют законами логики. Логические  выражения Алгебраические  выражения Переместительный закон (коммутативный) A Ú  B = B Ú  A A + B = B + A A Ù  B = B  Ù A A ∙ B = B ∙ A Сочетательный закон (ассоциативный) (A  Ú  B)  Ú  C = A Ú   (B  Ú  C) (A + B) + C = A + (B + C) (A  Ù  B)  Ù  C = A  Ù  (B  Ù  C) (A ∙ B) ∙ C = A ∙ (B ∙ C) Распределительный закон (дистрибутивный) (A Ú B) Ù C = (A Ù C) Ú  (B Ù C) (A + B) ∙ C = (A ∙ C) + (B ∙ C) (A Ù B) Ú  C = (A Ú  C) Ù (B Ú  C) аналога нет Закон инверсии   или формулы де Моргана

 

27

14

f0 0 0 0 0 константа 0 f1 0 0 0 1 конъюнкция X и Y f2 0 0 1 0 функция запрета по Y f3 0 0 1 1 переменная X f4 0 1 0 0 функция запрета по X f5 0 1 0 1 переменная Y f6 0 1 1 0 функция неравнозначности (сложение по модулю два) f7 0 1 1 1 дизъюнкция X и Y f8 1 0 0 0 стрелка Пирса f9 1 0 0 1 функция равнозначности f10 1 0 1 0 инверсия Y f11 1 0 1 1 импликация от X к Y f12 1 1 0 0 инверсия X f13 1 1 0 1 импликация от Y к X f14 1 1 1 0 штрих Шеффера f15 1 1 1 1 константа 1  4.2. Логические схемы

Закон двойного отрицания Закон исключения констант Для логического сложения Х Ú  0 = Х                          Х Ú  1 = 1 Для логического умножения Х Ù 0 = 0                             Х Ù 1 = Х Закон идемпотентности (от лат. idem potens – равносильный) Для логического сложения Х Ú  Х = Х Для логического умножения  Х Ù Х = Х Закон противоречия     Невозможно, чтобы противоречивые высказывания были одновременно истинными Закон исключения третьего Из двух противоречивых высказываний об одном и том же предмете одно высказывание истинно, а второе – ложно, третье не дано. Закон поглощения

 

26

15

F0 = 0(постоянная, не зависит от x, x – фиктивная переменная),             F3 = 1(постоянная, не зависит от x, x – фиктивная переменная),            F 1 = x,  F2 =, в f1 и f2    x – существенная переменная. Пусть F – функция двух переменных. Ее возможные значения приведены в таблице 3. Таблица 3. 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 Каждая ФАЛ  обозначает одну из 16 возможных логических операций над двумя переменными  и, имеет свою таблицу истинности, собственное название и условное обозначение. Таблица 4.

Закон исключения Используя законы логики, можно преобразовывать (упрощать) формулы. 2.3. Примеры решения задач и упражнений. Пример 1. Упростите формулу.  Решение. . Пример 2. Докажите тождественную истинность формулы: . Решение.

 

25

16

1,xi,xi+1,…,xn,что f(a1,…,ai-1,0,ai+1,… an) ¹ f(a1,…,ai-1,1,ai+1,… an). В этом случае переменная xi называется существенной, в противном случае – несущественной, или фиктивной. Очевидно, что постоянные функции не имеют существенных переменных. Логические выражения n двоичных переменных с помощью конечного числа логических операций можно рассматривать как некоторую функцию, отражающую взаимную связь между входными и выходными переменными. Логические операции конъюнкции  и дизъюнкции  можно представить простейшими функциями вида:  и . Эти функции называются аналогично логическим операциям – функциями И и ИЛИ. Такие ФАЛ подобно логическим выражениям могут быть заданы аналитическим и табличным способами. При аналитическом способе ФАЛ задается в виде логических выражений, получаемых путем логических преобразований с помощью законов и правил Булевой алгебры. При табличном способе ФАЛ задается таблицей истинности, где число всех возможных наборов (комбинаций) аргументов конечно. Если число аргументов ФАЛ равно n, то число их возможных наборов , а число различных функций , тогда при n = 1,  F = = 4, а   при n =2, F = =16. Пусть F – функция одной переменной. Ее возможные значения приведены в таблице 2. Таблица 2. x F0 F1 F2 F3 0 0 0 1 1 1 0 1 0 1

Получили двоичный набор, состоящий из единиц. Значит, формула тождественно истинна. Пример 3. Докажите эквивалентность формул:  и . Решение. Для доказательства необходимо построить таблицы истинности этих формул, и если их двоичные наборы совпадут, то их эквивалентность будет доказана. Получаем в последнем столбце одинаковые двоичные наборы. Значит, формулы эквивалентны.

 

24

17

Формулы алгебры логики являются функцией входящих в нее элементарных высказываний, ее аргументы принимают два значения: 0 и 1, при этом значение формулы может быть равно 0 или 1.             Определение 1. Функцией алгебры логики f(x1,x2,…,xn) от nпеременных x1,x2,…,xn (или функцией Буля) называется функция nпеременных, принимающая значения 0, 1, аргументы которой также принимают значения 0 и 1.             Функция f(x1,x2,…,xn) задается своей истинностной таблицей (табл. 1) Таблица 1. x1 x2 … xn-1 xn f(x1,x2,…,xn) 0 0 … 0 0 f(0,0,…,0,0) 1 0 … 0 0 f(1,0,…,0,0) … … … … … 1 1 1 1 0 f(1,1,…,1,0) 1 1 1 1 1 f(1,1,…,1,1)             Из этой таблицы видно, что число различных двоичных наборов длины n x1,x2,…,xn конечно и равно 2n.             Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из  строк, т.е. принимает  значений. Общее число наборов из 0 и 1 длины  равно . Это число равно числу различных функций алгебры логики n переменных.        Функция алгебры логики f(x1,…,xi-1,xi,xi+1,…,xn) зависит существенным образом от аргумента xi, если существуют такие значения  a1,…,ai-1,ai,ai+1,… an переменных x1,…,xi-

Пример 4. Проверить, является ли тавтологией формула: . Решение. Упростим данную формулу, используя известные соотношения: ,  ,  ,  . Получаем:  =  = = == Таким образом, формула является тавтологией. Пример 5.  Решите логическую задачу. Перед сдачей вступительных экзаменов в институт Миша предполагал, что: если он сдаст математику, то информатику он сдаст только при условии, что не завалит диктант; не может быть, чтобы он завалил и диктант, и математику; достаточное условие завала по информатике — это двойка по диктанту. После сдачи экзаменов оказалось, что из трех высказанных предположений только одно было ложным. Как Миша сдал экзамены? Введем обозначения: M – Миша сдал математику, I – Миша сдал информатику, D – Миша написал диктант. Тогда из условия задачи: Составим таблицу истинности для функций F1, F2, F3: M I D F1 F2 F3 0 0 0 1 0 1 0 0 1 1 1 1

 

23

18

X Y F(X,Y) 0 0 0 0 1 1* 1 0 1* 1 1 0 2. Выпишем для каждой отмеченной строки конъюнкцию всех пере­менных следующим образом: если значение некоторой переменной в дан­ной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: — для  2-й строки;   — для  3-й строки. 3. Все полученные конъюнкции свяжем в дизъюнкцию:   Для СКНФ. 1. Отметим те строки таблицы истинности, в последнем столбце ко­торых стоит 0: X Y F(X,Y) 0 0 0* 0 1 1 1 0 1 1 1 0* 2. Выпишем для каждой отмеченной строки дизъюнкцию всех пере­менных следующим образом: если значение некоторой переменной в дан­ной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание:  — для  1-й строки;   — для  4-й строки. 3. Все полученные дизъюнкции свяжем в конъюнкцию:   Если мы хотим построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ или СДНФ этой функции. Тема 4. Функции алгебры логики (булевы функции) 4.1. Определение функций алгебры логики.

0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 Решение выделено. Миша не сдал экзамены. Тема 3.Совершенные нормальные формы для формул логики высказываний 3.1. Дизъюнктивная и  конъюнктивная нормальные формы. Любая формула логики высказываний может иметь много представлений в виде ДНФ и КНФ. Простой конъюнкцией (элементарной) называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание).  Например, . Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, . Простой дизъюнкцией (элементарной) называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Например, . Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций.  Например, . 3.2.Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

 

22

19

0 1 0 0* 1 0 1 1 1 1 0 1 2. Выпишем для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно  1, то ее отрицание: для 2-й строки . 3. Все полученные дизъюнкции свяжем в конъюнкцию:  4. Упрощаем формулу, применяя законы логики (если это необходимо). Пример 2. Запишите СДНФ и СКНФ по  следующей таблице истинности. X Y F(X,Y) 0 0 0 0 1 1 1 0 1 1 1 0 Решение.    Для СДНФ. 1. Отметим те строки таблицы истинности, в последнем столбце ко­торых стоят 1:

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

 

	если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно  0, то ее отрицание. 3. Все полученные конъюнкции связать в дизъюнкцию:  4. Упрощаем формулу, применяем законы логики (если это необходимо). Алгоритм получения СКНФ по таблице истинности 1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 0: 2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно  1, то ее отрицание:  3. Все полученные дизъюнкции связать в конъюнкцию:  4. Упрощаем формулу, применяем законы логики (если это необходимо). 3.3. Примеры решения задач и упражнений. Пример 1. Запишите СДНФ и СКНФ по  следующей таблице истинности.                                                  X Y 0 0 1 1  0 1 0 0 1 0 1 1 1 1 0 1 Решение.   Для СДНФ.				1. Отметим те строки таблицы истинности, в последнем столбце которых стоят 1: X Y 0 0 1 1* 0 1 0 0 1 0 1 1* 1 1 0 1* 2. Выпишем для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно  0, то ее отрицание: для 1-й строки   , для 3-й строки , для 4-й строки . 3. Все полученные конъюнкции свяжем в дизъюнкцию:  4. Упрощаем формулу, применяя законы логики. Для СКНФ. 1. Отметим те строки таблицы истинности, в последнем столбце которых стоят 0: X Y 0 0 1 1
		20				21