Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Другие методич. материалы / Учебное пособие Алгебра логики
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Математика

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

библиотека
материалов


ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ - ТЕХНИКУМ

«ШЕНТАЛИНСКОЕ МЕДИЦИНСКОЕ УЧИЛИЩЕ»






Учебное пособие


Дисциплина: Элементы математической логики




Раздел 2: «Алгебра логики»














Шентала

2013 г.





Одобрено ЦМК «Общих гуманитарных и социально-экономических и математических и естественнонаучных дисциплин »

Председатель

_______М.Б. Мутыгуллина

Протокол № ___

от «___»____________2013г.


Составлено в соответствии

с государственными требованиями к минимуму содержания и уровню подготовки выпускников

по специальности 230115

«Программирование в компьютерных системах»

Зам. директора по УР

___________ Е.В.Курганская

«___»____________2013г














Составитель: Панина Л.И.



















РЕЦЕНЗИЯ


на учебное пособие по разделу «Алгебра логики» дисциплины «Элементы математической логики»

преподавателя ГБОУ СПО ШМУ Л.И.Паниной



Учебное пособие составлено в соответствии с требованиями ФГОС СПО по специальности 230115 «Программирование в компьютерных системах» для студентов 2 курса и предназначено для аудиторной и самостоятельной подготовки студентов по дисциплине «Элементы математической логики» при изучении раздела «Алгебра логики». Учебное пособие рассмотрено и одобрено ЦМК ОГСЭ и ЕН дисциплин. Основой разработки пособия явилась Рабочая программа дисциплины.

Учебное пособие состоит из содержания, рекомендаций для студентов по работе с учебным пособием, пояснительной записки, теоретического материала по темам раздела «Алгебра логики» с примерами решения задач и упражнений, заданий для самостоятельного выполнения, списка использованных источников.

Название учебного пособия соответствует его содержанию.

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

В целом, учебное пособие подготовлено согласно Методическим рекомендациям по составлению учебно-методического пособия управляющего типа.


Рецензент:

методист ГБОУ СПО ШМУ _________М.В. Бурлягина





РЕКОМЕНДАЦИИ

для студентов по работе с учебным пособием


Уважаемые, студенты!


Это учебное пособие поможет Вам в подготовке к теоретическим и практическим занятиям по дисциплине «Элементы математической логики» при изучении раздела «Алгебра логики».


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


Для успешной работы с учебным пособием необходимо:

- внимательно ознакомиться с информационным материалом, который изложен по шести темам;

- ознакомиться с примерами решения задач и упражнений по каждой теме;

- затем приступить к выполнению заданий для самостоятельного решения.






При необходимости проконсультируйтесь с преподавателем.


Желаю удачи!





ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Данное учебное пособие составлено в соответствии с государственным образовательным стандартом по дисциплине «Элементы математической логики» для специальности 230115 «Программирование в компьютерных системах»


Целью создания учебного пособия является необходимость систематизации учебного материала согласно требованиям рабочей программы.

Основная цель учебного пособия – организовать и повысить качество самоподготовки студентов, а также оптимизировать проведение занятий по дисциплине «Элементы математической логики».

В результате изучения учебной дисциплины в области алгебры логики студент должен:

знать:

- основные принципы математической логики;

- формулы алгебры высказываний;

- методы минимизации алгебраических преобразований

уметь:

- формулировать задачи логического характера и применять средства математической логики для их решения.


Предполагается практическое осмысление тем на практических занятиях, в процессе которых студент должен закрепить и углубить теоретические знания в области алгебры логики.









Тема 1.Высказывания. Основные логические операции

1.1. Основное понятие математической логики

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

Высказывания 2), 3), 4) истинны, а высказывание 1) ложно.  Очевидно, предложение «Да здравствует Россия!» не является высказыванием. 
       
Различают два вида высказываний. 
        Высказывание, представляющее собой одно утверждение, принято называть
простым или элементарным. Примерами элементарных высказываний могут служить высказывания 1) и 2). 
        Высказывания, которые получаются из элементарных с помощью грамматических связок «не», «и», «или», «если .... то ...», «тогда и только тогда», принято называть
сложными или составными. 
        Так, высказывание 3) получается из простого высказывания «Сокол - рыба» с помощью отрицания «не», высказывание 4) образовано из элементарных высказываний «Число 6 делится на 2», «Число 6 делится на З», соединенных союзом «и».
 
        Аналогично сложные высказывания могут быть получены из простых высказываний с помощью грамматических связок «или», «тогда и только тогда».
 
        В алгебре логики все высказывания рассматриваются только с точки зрения их логического значения, а от их житейского содержания отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.
 
        Элементарные высказывания обозначаются малыми буквами латинского алфавита:
 х, у, z, ..., а, b, с, ...; истинное значение высказывания цифрой 1, а ложное значение - цифрой 0. 
        Если высказывание
 а истинно, то будем писать а = 1, а если а ложно, то а = 0.

1.2. Логические операции над высказываниями

Над высказываниями можно проводить логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

Определение: Отрицанием высказывания А называется высказывание hello_html_m15e2cdcc.gif , которое истинно, если А ложно, и ложно, если А истинно.

Высказывание hello_html_m15e2cdcc.gifчитается так: «не А».

Таблица истинности для hello_html_m15e2cdcc.gif

А

hello_html_m15e2cdcc.gif

1

0

0

1

Здесь: 1 – истина, 0 – ложь.

Примеры:

1. Х: треугольник АВС – остроугольный. Х: неверно, что треугольник АВС – остроугольный. Это все равно, что: Х: треугольник АВС – прямоугольный или тупоугольный

2. А: Иванова М. на экзамене по математике получила 4. hello_html_m15e2cdcc.gif: Неверно, что Иванова М. по математике получила 4.


Определение: Дизъюнкцией высказывания А и В называется высказывание Аhello_html_m24ce8d55.gifВ, истинное при условии, что хотя бы одно из высказываний А или В истинно.

Его читают «А или В».

Таблица истинности для Аhello_html_m24ce8d55.gifВ

А

В

Аhello_html_m24ce8d55.gifВ hello_html_m53d4ecad.gif

0

0

0

0

1

1

1

0

1

1

1

1


Примеры: 1. По математике будет зачет или экзамен.

2. 10 – простое или составное число.


Определение: Конъюнкцией высказываний А и В называется высказывание Аhello_html_m6ea3206b.gifВ, которое истинно лишь при условии, что истинны оба высказывания и А, и В.

Высказывание А hello_html_m6ea3206b.gif В читается «А и В».

Таблица истинности

А

В

Аhello_html_m6ea3206b.gifВ

0

0

0

0

1

0

1

0

0

1

1

1


Примеры: 1. На этот раз ответчик явился и суд состоялся. – истина

2. В прямоугольном треугольнике сумма двух любых углов больше или равна третьего угла и гипотенуза меньше катета. – ложь


Определение: Импликацией высказываний А и В называется высказывание Аhello_html_1b730b13.gifВ, ложное лишь при условии, что А истинно, а В ложно.

Его читают: «Если А, то В».


Таблица истинности

А

В

Аhello_html_7d891242.gifВ

0

0

1

0

1

1

1

0

0

1

1

1

Примеры: 1. Если я сдам зачет, то пойду в кино.

2. Если треугольник равнобедренный, то углы при его основании равны.


Определение: Эквиваленцией высказываний А и В называется высказывание Аhello_html_39bcdcee.gifВ, истинное в том и только в том случае, когда А и В имеют одну и ту же истинность (т.е. либо оба истинны, либо оба ложны).

Читают: «А тогда и только тогда, когда В» или «А необходимо и достаточно для В»

Таблица истинности

А

В

Аhello_html_3783f81b.gifВ

0

0

1

0

1

0

1

0

0

1

1

1

Таблица истинности для всех логических операций:

hello_html_m4cb716bb.png

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


Строгая дизъюнкция или Сложение по модулю «2», соответствует оборотам речи «или…, или…» или «либо…, либо…», и обозначаетсяhello_html_m6c35447b.gif


hello_html_3c557217.png

hello_html_m7492d8a1.png


Тема 2. Формулы и законы алгебры логики

2.1. Формулы логики

    С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой.

Логическую формулу можно определить следующим образом:

  1. Всякая логическая переменная (x, y, z ,..) и символы истина (1) и ложь (0) — формулы.

  2. Если F - формула, то hello_html_2989d3f1.png - также формула.

  3. Если F1 и F2 - формулы, то hello_html_772f24b2.pnghello_html_687ce0ae.pnghello_html_675a43ab.pnghello_html_88ef1c5.png - тоже формулы

  4. Никаких других формул в алгебре логики нет.




Формализовать - значит:

1) Каждому простому предложению сопоставить элементарную формулу.

2) Если предложение составное, то выделяем простые предложения, заменяем их на элементарные формулы, вместо связок расставляем знаки логических операций.

3) Если нужно, расставляем круглые скобки.

Пример: Рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Обозначим буквой A высказывание: "купить яблоки", буквой B - высказывание: "купить абрикосы",буквой C - высказывание: "испечь пирог". Тогда высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог"формализуется в виде формулы: (A v B) hello_html_3085d4e.jpg C.

Некоторые формулы принимают значение “истина” при любых значениях истинности входящих в них переменных. Такие формулы называются тождественно истинными формулами или тавтологиями.

Тавтология - формула, которая истинна при любом наборе значений входящих в неё переменных (тождественно истинная формула). Например, hello_html_23418fad.gif, hello_html_1cde2aa2.gif, hello_html_36600005.gif

Некоторые формулы принимают значение “ложно” при любых значениях истинности входящих в них переменных. Такие формулы называются тождественно ложными формулами или противоречиями.

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

Логические операции имеют следующий приоритет: действия в скобках, инверсия , hello_html_48dce19e.gif,hello_html_m1b1b7e1d.gif, hello_html_481011d1.gif.

Пример:hello_html_m76742ed6.png

hello_html_m3e2e8cc1.png

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

Обозначение. AB.

Пример.

hello_html_m38f20a41.png.









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)

аналога нет

Закон инверсии или формулы де Моргана

hello_html_m45043c42.gif

hello_html_m33f9a8ae.gif

Закон двойного отрицания

hello_html_m78c76733.gif

Закон исключения констант

Для логического сложения

Х 0 = Х Х 1 = 1


Для логического умножения

Х 0 = 0 Х 1 = Х


Закон идемпотентности (от лат. idem potens – равносильный)

Для логического сложения Х Х = Х

Для логического умножения Х Х = Х

Закон противоречия

hello_html_m2941ef.gifНевозможно, чтобы противоречивые высказывания были одновременно истинными

Закон исключения третьего

hello_html_m28178a94.gifИз двух противоречивых высказываний об одном и том же предмете одно высказывание истинно, а второе – ложно, третье не дано.



Закон поглощения

hello_html_m66cbb43b.gif

Закон исключения

hello_html_m81b4458.gif




Используя законы логики, можно преобразовывать (упрощать) формулы.




2.3. Примеры решения задач и упражнений.


Пример 1. Упростите формулуhello_html_m124598ae.gif.

Решение. hello_html_5e91b32.gif.


Пример 2. Докажите тождественную истинность формулы: hello_html_1a7fe988.gif.

Решение.

hello_html_67852bfb.png

Получили двоичный набор, состоящий из единиц. Значит, формула тождественно истинна.

Пример 3. Докажите эквивалентность формул: hello_html_36498beb.gif и hello_html_m6bfc6ac4.gif.

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



hello_html_219479b3.png

hello_html_m651bbfaf.png

Получаем в последнем столбце одинаковые двоичные наборы. Значит, формулы эквивалентны.

Пример 4. Проверить, является ли тавтологией формула: hello_html_11371666.gif.

Решение. Упростим данную формулу, используя известные соотношения: hello_html_70c99fd8.gif, hello_html_430b606a.gif, hello_html_m3d153074.gif, hello_html_1d6935ce.gif.

Получаем:

hello_html_11371666.gif = hello_html_m53d4ecad.gifhello_html_5474aa19.gif = hello_html_28351c04.gifhello_html_m4c4c914b.gif=hello_html_28351c04.gifhello_html_m5d7ba02d.gif =hello_html_28351c04.gifhello_html_337ab8a2.gif=hello_html_28a6e128.gif

Таким образом, формула является тавтологией.

Пример 5. Решите логическую задачу.

Перед сдачей вступительных экзаменов в институт Миша предполагал, что:

если он сдаст математику, то информатику он сдаст только при условии, что не завалит диктант;

не может быть, чтобы он завалил и диктант, и математику;

достаточное условие завала по информатике — это двойка по диктанту.

После сдачи экзаменов оказалось, что из трех высказанных предположений только одно было ложным. Как Миша сдал экзамены?

Введем обозначения:

M – Миша сдал математику,

I – Миша сдал информатику,

D – Миша написал диктант.

Тогда из условия задачи:

hello_html_5e22910a.gif

Составим таблицу истинности для функций F1, F2, F3:

M

I

D

F1

F2

F3

0

0

0

1

0

1

0

0

1

1

1

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. Дизъюнктивная и конъюнктивная нормальные формы.


Любая формула логики высказываний может иметь много представлений в виде ДНФ и КНФ.

Простой конъюнкцией (элементарной) называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание).  Например, hello_html_m106de0dc.png.

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

Простой дизъюнкцией (элементарной) называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Например, hello_html_m360dd990.png.

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


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

Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

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

Перечислим свойства совершенства для СДНФ:

1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию.
2. Все логические слагаемые различны.
3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание.
4. Ни одно слагаемое не содержит одну и ту же переменную дважды.

Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, у которой в каждую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке. 

Перечислим свойства совершенства для СКНФ:

  • Каждый логический множитель формулы содержит все переменные, входящие в функцию.

  • Все логические множители различны.

  • Ни один множитель не содержит одновременно переменную и ее отрицание.

  • Ни один множитель не содержит одну и ту же переменную дважды.

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

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1:

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно  0, то ее отрицание.

3. Все полученные конъюнкции связать в дизъюнкцию: 

4. Упрощаем формулу, применяем законы логики (если это необходимо).

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

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 0:

2. Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно  1, то ее отрицание: 

3. Все полученные дизъюнкции связать в конъюнкцию: 

4. Упрощаем формулу, применяем законы логики (если это необходимо).




3.3. Примеры решения задач и упражнений.

Пример 1. Запишите СДНФ и СКНФ по следующей таблице истинности.

X

Y

hello_html_1024b216.png

hello_html_m3de3993c.png

0

0

1

1

0

1

0

0

1

0

1

1

1

1

0

1

Решение. Для СДНФ.

1. Отметим те строки таблицы истинности, в последнем столбце которых стоят 1:

X

Y

hello_html_1024b216.png

hello_html_m3de3993c.png

0

0

1

1*

0

1

0

0

1

0

1

1*

1

1

0

1*

2. Выпишем для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно  0, то ее отрицание: для 1-й строки   hello_html_10b5083d.png, для 3-й строки hello_html_m200b0de5.png, для 4-й строки hello_html_m58601d74.png.

3. Все полученные конъюнкции свяжем в дизъюнкцию: hello_html_m2e4a4936.png

4. Упрощаем формулу, применяя законы логики.

hello_html_114beb04.png

Для СКНФ.

1. Отметим те строки таблицы истинности, в последнем столбце которых стоят 0:

X

Y

hello_html_1024b216.png

hello_html_m3de3993c.png

0

0

1

1

0

1

0

0*

1

0

1

1

1

1

0

1



2. Выпишем для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно  1, то ее отрицание: для 2-й строки hello_html_m200b0de5.png.

3. Все полученные дизъюнкции свяжем в конъюнкцию: hello_html_m3de3993c.png

4. Упрощаем формулу, применяя законы логики (если это необходимо).






Пример 2. Запишите СДНФ и СКНФ по следующей таблице истинности.

X

Y

F(X,Y)

0

0

0

0

1

1

1

0

1

1

1

0

Решение. Для СДНФ.

1. Отметим те строки таблицы истинности, в последнем столбце ко­торых стоят 1:

X

Y

F(X,Y)

0

0

0

0

1

1*

1

0

1*

1

1

0

2. Выпишем для каждой отмеченной строки конъюнкцию всех пере­менных следующим образом: если значение некоторой переменной в дан­ной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: hello_html_m5313f3e.gif— для 2-й строки; hello_html_292aca42.gif — для 3-й строки.

3. Все полученные конъюнкции свяжем в дизъюнкцию: hello_html_6a50f81a.gif

Для СКНФ.

1. Отметим те строки таблицы истинности, в последнем столбце ко­торых стоит 0:

X

Y

F(X,Y)

0

0

0*

0

1

1

1

0

1

1

1

0*

2. Выпишем для каждой отмеченной строки дизъюнкцию всех пере­менных следующим образом: если значение некоторой переменной в дан­ной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание: hello_html_1713315f.gif— для 1-й строки; hello_html_m641ffc42.gif — для 4-й строки.

3. Все полученные дизъюнкции свяжем в конъюнкцию: hello_html_626a7f42.gif

Если мы хотим построить формулу некоторой функции по таблице истинности этой функции, то всегда можно получить СКНФ или СДНФ этой функции.

Тема 4. Функции алгебры логики (булевы функции)

4.1. Определение функций алгебры логики.


Формулы алгебры логики являются функцией входящих в нее элементарных высказываний, ее аргументы принимают два значения: 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.

 

            Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из hello_html_5bef1d05.png строк, т.е. принимает hello_html_5bef1d05.png значений. Общее число наборов из 0 и 1 длины hello_html_5bef1d05.png равно hello_html_m3771de71.png. Это число равно числу различных функций алгебры логики n переменных.

  Функция алгебры логики f(x1,…,xi-1,xi,xi+1,…,xn) зависит существенным образом от аргумента xi, если существуют такие значения  1,…,i-1,i,i+1,… n переменных x1,…,xi-

1,xi,xi+1,…,xn,что f(1,…,i-1,0,i+1,… n f(1,…,i-1,1,i+1,… n). В этом случае переменная xi называется существенной, в противном случае – несущественной, или фиктивной. Очевидно, что постоянные функции не имеют существенных переменных.

Логические выражения n двоичных переменных с помощью конечного числа логических операций можно рассматривать как некоторую функцию, отражающую взаимную связь между входными и выходными переменными. Логические операции конъюнкции hello_html_f6d3964.png и дизъюнкции hello_html_1f3c100b.png можно представить простейшими функциями вида: hello_html_2e77b0ee.png и hello_html_m25ef7bdb.png. Эти функции называются аналогично логическим операциям – функциями И и ИЛИ. Такие ФАЛ подобно логическим выражениям могут быть заданы аналитическим и табличным способами.

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

При табличном способе ФАЛ задается таблицей истинности, где число всех возможных наборов (комбинаций) аргументов конечно. Если число аргументов ФАЛ равно n, то число их возможных наборов hello_html_1da346bb.png, а число различных функций hello_html_m626332bf.png,

тогда при n = 1, F = hello_html_m2a6dff6d.gif= 4, а при n =2, F = hello_html_m4e57e44a.gif=16.

Пусть F – функция одной переменной. Ее возможные значения приведены в таблице 2.

 

Таблица 2.

x

F0

F1

F2

F3

0

0

0

1

1

1

0

1

0

1

 

            F0 = 0(постоянная, не зависит от xx – фиктивная переменная),

            F3 = 1(постоянная, не зависит от xx – фиктивная переменная),

           F 1 = x, F2 =hello_html_m6b9bf3c6.gif, в f1 и f2  x – существенная переменная.

Пусть F– функция двух переменных. Ее возможные значения приведены в таблице 3.

Таблица 3.

hello_html_3dca8b3c.png

hello_html_m472d21ad.png

hello_html_13af6f1a.png

hello_html_72490f9d.png

hello_html_m55274281.png

hello_html_11c3257e.png

hello_html_m612e7df0.png

hello_html_27487ae4.png

hello_html_m5ebabd73.png

hello_html_652f0a98.png

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


hello_html_2d74b0fc.png

hello_html_c2894fd.png

hello_html_mfeee532.png

hello_html_m29887b3b.png

hello_html_504a4538.png

hello_html_mb56899e.png

hello_html_673f8aa1.png

hello_html_m383433bf.png

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

Каждая ФАЛ hello_html_m38559dcd.png обозначает одну из 16 возможных логических операций над двумя переменными hello_html_3dca8b3c.png иhello_html_m472d21ad.png, имеет свою таблицу истинности, собственное название и условное обозначение.

Таблица 4.

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. Логические схемы       

hello_html_m76675055.png

Функция "И" равна единице, если равны единице ВСЕ ее аргументы.

Функция "ИЛИ" равна единице, если равен единице ХОТЯ БЫ один аргумент.

Функция "ИСКЛЮЧАЮЩЕЕ ИЛИ" (сумма по модулю 2) равна единице, если равен единице ТОЛЬКО один ее аргумент.

Тема 5. Многочлен Жегалкина.

5.1. Полиномиальное разложение булевых функций

 

Определение.  Под полиномом булевой функции F понимается представление F  посредством сложения по модулю два попарно различных элементарных конъюнкций. Иначе такое представление F называется полиномиальным разложением или полиномиальной нормальной формой (ПНФ) функции F.

Например, полиномом булевой функции F, заданной вектором значений таблицы истинности w(F)=(00100111),  является следующее выражение hello_html_m2d588c4b.png.

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

В приведенном выше примере длина полинома функции F равна 3, а степень – 2.

Определение. Полином функции F, состоящий только из полных элементар­ных конъюнкций, называется совершенной ПНФ (СПНФ). По аналогии с СДНФ такое представление конкретной булевой функции F явля­ется единственным.

Полином F, содержащий наименьшее число слагаемых среди всех полиномов, реализующих функцию F, называется кратчайшей ПНФ (КрПНФ).Полином функции F, содержащий наименьшее число вхождений литералов, называется минимальной ПНФ.

 

5.2. Разложение булевых функций в канонический полином Жегалкина

 

Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логи­ческих схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА.

Определение. Полином булевой функции F, в слагаемые которого все переменные F входят только без отрица­ния или только с отрицанием, называется монотонно-поляризован­ным. Причем в первом случае полином функции F называется поло­жительно-поляризованный и обозначается черезP(F), а во втором случае - отрицательно-поляризованным и обозначается через Q(F). Полином P(F) иначе называется каноническим полиномом Жегалкина (или в зарубежной научно-технической литературе - формой Рида-Мюллера).

Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) полиномы P(F) и Q(F) имеют вид:

hello_html_1e6ab595.png,

hello_html_m6b4077e1.png.

Отметим некоторые свойства монотонно-поляризованных поли­номов P(F) и Q(F) булевой функции hello_html_m7ec5d55a.png:

1. Полиномы P(F) и Q(F) являются для булевой функции F единственными.

2. Полиномы P(F) и Q(F) имеют степень n тогда и только тогда, когда

    таблица истинности функции F содержит нечетное число единиц.

3. Число слагаемых полинома P(F) (Q(F)) четно тогда и только тогда, когда

   hello_html_27f75dae.png (соответственно hello_html_m61d469b6.png).

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

Опишем метод построения канонического поли­нома Жегалкина P(F) путем преобразования СДНФ для произвольных булевых функций n  пе­ременных F, заданных посредством таблицы истинности.

Предварительно отметим основные свойства логической опе­рации сложения по модулю два, которые используются при описа­нии метода.

 

Имеет место

hello_html_m333b003d.png                 (1)

hello_html_m29dd7ca5.png                                                             (2)

 

hello_html_m5ad7ddd3.png                                                        (3)

 

hello_html_m43bb9b6b.png                                                         (4)

 

hello_html_m147e1c5b.png,       если  hello_html_25238241.png                            (5)

 

hello_html_m5f4cd643.png,                  (6)

если  hello_html_50f62ca5.png для   hello_html_m322382f8.png, hello_html_7528d0c1.png hello_html_2cea4802.png.

Метод построения полинома P(F) заключается в последова­тельном выполнении следующих действий:

1) выписывается СДНФ булевой функции F;

2) на основе применения (6) СДНФ F пре­образуется в СПНФ функции F;

3) в СПНФ все переменные с отрицанием заменяют­ся по формуле (2);

4) в скобочной форме осуществляется раскрытие скобок согласно (3);

5) из полученного выражения удаляются попарно одинаковые слагаемые в соответствии с (1);

6) полу­ченное выражение обозначается через P(F).

 Приведем полиномы Жегалкина элементарных булевых функций

hello_html_4f1111d0.gif

hello_html_22bcec45.gif

hello_html_m7ea5a5bc.gif

hello_html_m6205a1a1.gif

hello_html_70a4637a.gif


5.3. Примеры решения задач и упражнений.


Рассмотрим на примерах построение СПНФ, используя преобразование СДНФ булевой функции и канонический полином Жегалкина.

 

Пример 1. Составить СПНФ булевой функции, заданной вектором значений таблицы истинности w(F)=(10010010). 

 

Решение. Так как вектор значений заданной булевой функции имеет 8=23 разрядов, следовательно, булевой функции соответствует следующая таблица истинности:

 

hello_html_m10683dc2.png

hello_html_m440a1207.png

hello_html_3f1c596d.png

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

 

СДНФ данной булевой функции, построенная  по таблице истинности будет иметь вид: hello_html_14e30fd7.png.

 

Заменим операцию дизъюнкции на операцию сложения по модулю два по формуле:  hello_html_m4ce3d71d.png. При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю (при построении СДНФ по таблице истинности это очевидно ― все наборы отличаются хотя бы по отрицанию одной переменной). Следовательно, СПНФ будет иметь вид:

hello_html_m7d62a7e3.png.

Ответ: hello_html_m7d62a7e3.png

 

Пример 2. Составить СПНФ булевой функции, если СДНФ данной булевой функции, имеет вид: hello_html_79530ec2.png.

 

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

hello_html_m6705c3ba.png


Пример 3. Составить канонический поли­ном Жегалкина P(F) булевой функции, если СДНФ данной булевой функции, имеет вид: hello_html_79530ec2.png.

 

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

hello_html_6cae2656.png.

Все переменные с отрицанием заменяем по формуле (2), затем раскрываем скобки и из полученного выражения удаляем попарно одинаковые слагаемые в соответствии с (1):

hello_html_568f9991.png

hello_html_7c9fcea2.png

hello_html_3fe2625f.png.

Ответ: P(F) hello_html_3fe2625f.png.

Тема 6.Основные классы функций алгебры логики.

Пусть имеется некоторый набор K, состоящий из конечного числа булевых функций. Суперпозицией функций из этого набора называются новые функции:

- полученные с помощью конечного числа применения двух операций;

- можно переименовать любую переменную, входящую в функцию из K;

- вместо любой переменной можно поставить функцию из набора K или уже образованную ранее суперпозицию.

Суперпозицию еще иначе называют сложной функцией.

Пример 7.1. Если дана одна функция х|y (штрих Шеффера), то ее суперпозициями, в частности, будут следующие функции x|x, x|(x|y), x|(y|z) и т. д.

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

Набор функций называется полным, если его замыкание совпадает со всеми логическими функциями. Иначе говоря, полный набор – это множество таких функций, через которые можно выразить все остальные булевы функции.

Неизбыточный полный набор функций называется базисом (“неизбыточный” означает, что если какую-то функцию удалить из набора, то этот набор перестанет быть полным).

Пример 7.2. Конъюнкция, дизъюнкция и отрицание являются полным набором, но не являются базисом, так как это набор избыточен, поскольку с помощью правил де Моргана можно удалить конъюнкцию или дизъюнкцию.

Любую функцию можно представить в виде полинома Жегалкина. Ясно, что функции конъюнкция, сложение по модулю 2 и константы 0 и 1 являются полным набором, но эти четыре функции также не являются базисом, поскольку 1+1=0, и поэтому константу 0 можно исключить из полного набора (для построения полиномов Жегалкина константа 0 необходима, поскольку выражение “1+1” не является полиномом Жегалкина).

Легко видеть, что одним из способов проверки полноты какого-то набора К является проверка того, что через функции из этого набора выражаются функции другого полного набора (можно проверить, что через функции из К можно выразить конъюнкцию и отрицание или дизъюнкцию и отрицание).

Существуют такие функции, что одна такая функция сама является базисом (здесь достаточно проверить только полноту, неизбыточность очевидна). Такие функции называются шефферовскими функциями. Это название связано с тем, что штрих Шеффера является базисом. Напомним, что штрих Шеффера определяется следующей таблицей истинности:

hello_html_m5c497873.png

Так как очевидно hello_html_m7b7a5fca.png, т. е. отрицание является суперпозицией штриха Шеффера, а дизъюнкция тогда hello_html_m12ae231b.png, штрих Шеффера сам является базисом. Аналогично, стрелка Пирса является шефферовской функцией.

Заметим, что вычислительное устройство чаще всего базируется на полном наборе функций (часто на базисах). Если в основе устройства лежат конъюнкция, дизъюнкция и отрицание, то для этих устройств важна проблема минимизации ДНФ; если в основе устройства лежат другие функции, то полезно уметь алгоритмически минимизировать выражения через эти функции.

Перейдем теперь к выяснению полноты конкретных наборов функций. Для этого перечислим 5 важнейших классов функций:

  • Т0 – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (Т0 – это класс функций, сохраняющих 0);

  • Т1 – это набор всех логических функций, которые на единичном наборе принимают значение 1 (Т1 – это класс функций, сохраняющих единицу) (заметим, что число функций от п переменных принадлежащих классам Т0 и Т1 равно 22n-1);

  • L – класс линейных функций т. е. функций, для которых полином Жегалкина содержит только первые степени переменных;

  • М – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 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), является монотонной);

Класс S – класс самодвойственных функций. Функция п переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, т. е. самодвойственная функция f(x1, x2,…,xn) удовлетворяет условию f (x1,x2, ..., xn ) =hello_html_m21fef1ad.gif. Например, функции 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

+

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, то 8
3  500”.
е). “Если 2· 2=4, то 7
2 =81”.
ж). “Если телепатия существует, то некоторые физические законы требуют пересмотра”.

3. По заданной таблице истинности составить логическое выражение - формулу и на ее основе построить функциональную схему.

Уровень А: 1). 2).

X

Y

F


X

Y

F

0

0

1


0

0

1

0

1

1


0

1

1

1

0

0


1

0

0

1

1

1


1

1

0

Ответ: А - hello_html_m46f95f60.gif, Б - hello_html_115ea194.gif

Уровень Б: 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). - hello_html_m1676cdf4.gif, 2). - hello_html_5d3a5614.gif


Уровень В:


a

b

c

hello_html_1ff3bd40.gif

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

hello_html_m7183cb62.gif

Ответ:


4. Является ли высказывание (XY)(YX) тавтологией. Выписать СКНФ и СДНФ.

5. Установить эквивалентны ли высказывания. Выписать СКНФ или СДНФ.

а) hello_html_65f5b0f5.gifhello_html_14dbdb44.gifhello_html_315c611a.gif

б) hello_html_m745816b.gifhello_html_602d5031.gifhello_html_m65d3f884.gif

.

6. Напишите полином Жегалкина для формул.


а)hello_html_m73c4c6d2.gif; б)hello_html_b915fd1.gif


7.Является ли функция hello_html_m4182dbbe.gif самодвойственной?


8. Определите монотонность данных функций.


а) hello_html_57623dce.gif б) hello_html_m77c71c5d.gif
















Рекомендуемая литература.


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

39





3

38





4

37





5

36





6

35





7

34





8

33





9

32





10

31





11

30



12

29








13

28





14

27





15

26





16

25





17

24





18

23





19

22





20

21



Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 03.10.2015
Раздел Математика
Подраздел Другие методич. материалы
Просмотров833
Номер материала ДВ-028639
Получить свидетельство о публикации
Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх