Высказывания и операции над ними.

Методические материалы

К изучению курса

«Дискретная математика»

Часть IV. Булевы функции

Лысьва, 2006

Мухаметьянов И.Т. Методические материалы к изучению курса «Дискретная математика». Часть IV. Булевы функции. - Лысьва: Издательство ЛФ ПГТУ, 2006. - 32 с.

Рецензент -

Данное пособие является одним из серии пособий по дискретной математике. Читатель в нём найдёт как теоретический материал, так и материал для практических занятий по теории булевых функций. Кроме того, в пособии приведены варианты для самостоятельной работы студентов (всего 30 вариантов), а также образцы оформления их решений.

Ó Мухаметьянов И.Т., 2006 г.

Ó Лысьвенский филиал Пермского государственного технического университета (ЛФ ПГТУ), 2006 г.

Содержание

Содержание……………………………………………………………………….3

Предисловие……………………………………………………………………...4

§1. Высказывания и операции над ними…………………………….……….5

1.1. Понятие высказывания……….…………………………………………..5

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

1.3. Дальнейшие логические операции над высказываниями……………..11

§2. Формулы алгебры логики. Таблицы истинности……………………...12

2.1. Формулы алгебры логики……………………………………………….12

2.2. Таблицы истинности……………………..…………………………..….13

2.3. Законы логики……………………………………………………………16

Логическое следование и равносильность формул.

Связь с булевыми алгебрами......................................................................18

3.1. Логическое следование и равносильность формул……………………18

3.2. Связь с булевыми алгебрами....................................................................21

§4. Нормальные формы. Двойственность…………...……………………...22

4.1. Дизъюнктивная нормальная форма.

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

4.2. Конъюнктивная нормальная форма.

Совершенная конъюнктивная нормальная форма…………………….25

§5. Булевы функции и их основные классы. Полином Жегалкина……..29

5.1. Понятие булевой функции и способы её задания..……………………29

5.2. Основные классы булевых функций.......................................................31

5.3. Полином Жегалкина……………………………………………………..35

5.4. Функциональная полнота…………………………………………….….35

§6. Минимизация булевых функций ……………………….………………..36

6.1. Проблема минимизации…………………………...….…………………36

6.2. Сокращённая ДНФ. Метод Квайна..........................................................36

6.3. Минимальная ДНФ. Таблица Квайна......................................................37

6.4. Метод Квайна-Мак-Класки......................................................................38

§7. Применение к релейно-контактным схемам ……………………….….36

Приложение 1. Варианты индивидуальных заданий………………….…..43

Приложение 2. Образец выполнения индивидуального задания………..60

Литература…………………………………………………...71

Предисловие

Предлагаемое читателю учебно-методическое пособие является одним из серии пособий по дискретной математике для студентов. Мы предполагаем выпустить эту серию в следующем составе:

Элементы теории множеств

Алгебраические структуры

Элементы теории графов

Булевы функции

Каждое пособие состоит из двух частей.

В первой части приводится необходимый теоретический материал в сокращённом виде (без доказательств), приводятся примеры решения задач технического характера для практических занятий и самостоятельной работы студентов, а также упражнения. Теоретические задачи в пособие мы не включили, так как ограниченность во времени для аудиторных занятий не позволяет, как правило, довести дело до рассмотрения таких задач. Поэтому желающих не ограничиваться техническими задачами мы отсылаем к источникам, которые приведены в списке литературы. Среди задач есть как заимствованные из различных сборников задач, так и составленные нами.

Вторая часть включает в себя приложения. Приложение 1 содержит варианты для индивидуальных самостоятельных работ. Они в значительной степени заимствованы из [4]. В приложении 2 мы приводим образцы выполнения индивидуального задания. В этой связи нам пришлось повторять изложение некоторых методов решения задач. Следует обратить внимание на то, что индивидуальная самостоятельная работа выполняется за рамками аудиторных часов, и поэтому при выполнении задания следует приводить подробные пояснения, с соответствующими ссылками на теоретический материал.

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

Высказывания и операции над ними.

1.1. Понятие высказывания. Понятие “высказывание” является первичным, оно не определяется, а лишь поясняется. Под высказыванием понимают повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно. Например, “Земля — планета солнечной системы” (истинное высказывание), “Луна — искусственный спутник Земли” (ложное высказывание), “4>5” (ложное высказывание), “4>3” (истинное высказывание), “ х²³0 для каждого действительного числа х” (истинное высказывание), “Существует действительное число х такое, что х²=-1” (ложное высказывание).

Любое высказывание либо истинно, либо ложно, и никакое высказывание не является одновременно истинным и ложным.

Имеются повествовательные предложения, которые не являются высказываниями. Например, повествовательное предложение “Сегодня хорошая погода” не является высказыванием, так как о нём нельзя однозначно судить, истинно оно или ложно.

Следующие предложения “Который час?”, “Да здравствует наука!” не являются высказываниями, так как они не являются повествовательными. Такие предложения, как, определения, также не являются высказываниями. Например, определение “Натуральное число называется чётным, если оно делится на 2” не является высказыванием. Однако, повествовательное предложение “Если число делится на 2, то оно чётное” — высказывание, и притом истинное. Повествовательное предложение ”Если натуральное число является чётным, то оно делится на 2” — также истинное высказывание.

Упражнение 1.1. Какие из следующих предложений являются высказываниями?

а) Пермь — столица Пермского края.

б) Студент технического университета.

в) Треугольник АВС подобен треугольнику А¢В¢С¢.

г) Земля есть спутник Юпитера.

д) 3+ - .

е) Кислород — газ.

ж) Каша — вкусное блюдо.

з) Математика — интересный предмет.

и) Картины Пикассо слишком абстрактны.

к) Железо тяжелее свинца.

л) Да здравствуют музы!

м) Треугольник называется равносторонним, если все его стороны равны.

н) Если в треугольнике все углы равны, то он равносторонний.

о) Сегодня плохая погода.

п) В романе А.Дюма “Граф Монте-Кристо” 179 персонажей.

р) Река Кама впадает в Каспийское море.

Решение. б) Это предложение не является высказыванием, потому что оно ничего не утверждает о студенте.

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

ж) Предложение не является высказыванием, так как понятие “вкусное блюдо” слишком неопределенно.

В логике высказываний (раздел математической логики) отвлекаются от смыслового содержания высказывания и приписывают каждому высказыванию его истинностное значение (“истина”, “ложь”), отождествляя высказывание с его истинностным значением. Эти истинностные значения — истина и ложь — называют логическими значениями высказываний.

Высказывания будем обозначать строчными буквами латинского алфавита а, b, c, ... , a₁, a₂, …,. Эти буквы называются пропозициональными переменными. Их логические значения (истина, ложь) обозначаются через соответственно буквами И и Л, или знаками 1 и 0, соответственно. Во многих приложениях принято именно последнее обозначение, которого будем придерживаться и мы.

Пусть А — высказывание. Если это высказывание истинно, то пишут А=1, если же оно ложно, то пишут А=0. Например, (3>2)=1; (2>5)=0; (2¹2)=0; (sin — периодическая функция)=1.

Упражнение 1.2. Укажите, какие из высказываний предыдущего упражнения истинные, а какие — ложные.

1.2. Основные логические операции над высказываниями. Из высказываний a, b, c, ... можно составить новые составные высказывания. Для этого используются следующие так называемые логические операции над высказываниями:

1) отрицание (Ø);

2) конъюнкция (&);

3) дизъюнкция (Ú);

4) импликация (®);

5) эквиваленция («).

Определение 1. Отрицанием высказывания a называется высказывание, обозначаемое символом Øa, которое является истинным, если a ложно, и ложным, если a истинно. Читается: “неверно, что a”, или, короче “не a”.

Например, для истинного высказывания “4>3” отрицанием будет ложное высказывание “неверно, что 4>3“, или короче “4 не больше 3”, которое обычно записывается так: Ø (4>3) или 4£3.

Зависимость логического значения отрицания ØА от логического значения высказывания А можно выразить наглядно с помощью следующей таблицы, называемой таблицей истинности отрицания:

В строках первого столбца таблицы указаны два возможных логических значения высказывания a: 1 (истина) и 0 (ложь), в строках второго столбца таблицы — соответствующие логические значения отрицания Øa: 0 (ложь) в первом случае и 1 (истина) — во втором.

Упражнение 1.3. Сформулируйте отрицания следующих высказываний; укажите значения истинности данных высказываний и их отрицаний:

а) Кама впадает в Каспийское море.

б) Число 36 не делится на число 6.

в) 8>5.

г) 5£8.

д) Все простые числа нечётны.

Упражнение 1.4. Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие — нет (объясните почему):

а) 3<4, 3>4.

б) 6<9, 6³9.

в) “Треугольник АВС прямоугольный”, “Треугольник АВС тупоугольный”.

г) “Натуральное число n чётно”, “Натуральное число n нечётно”.

д) “Функция f нечётна”, “Функция f чётна”.

е) “Все простые числа нёчетны”, “Все простые числа чётны”

ж) “Все простые числа нечётны”, “Существует простое чётное число”.

з) “Человеку известны все виды животных, обитающих на Земле”, “На Земле существует вид животных, не известный человеку”.

и) “Существуют иррациональные числа”, “Все числа рациональные”.

Решение. а) Высказывание “3>4” не является отрицанием высказывания “3<4” так как что требование не быть меньше 4 предполагает две возможности: быть равным 4 и быть больше 4. Таким образом, отрицанием высказывания “3>4” является высказывание “3£4”.

Упражнение 1.5. Следующие высказывания запишите без знака отрицания:

а) Ø(а<b); в) Ø(а³b);

б) Ø(а£b); г) Ø(а>b).

Определение 2. Конъюнкцией двух высказываний a и b называется высказывание, обозначаемое символом a&b, которое является истинным, если истинны оба высказывания a и b, и ложным, если ложно хотя бы одно из них. Читается: “a и b”. Высказывания a и b называются членами конъюнкции.

Например, для высказываний “3<8” и “8<10” конъюнкция “(3<8)&(8<10)” будет истинным высказыванием: “(3<8)&(8<10)=1 (это высказывание записывают короче: “3<8<10”).

Зависимость логического значения конъюнкции a&b от логических значений её членов a и b можно выразить следующей таблицей, называемой таблицей истинности конъюнкции:

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

Из определения 2 следует, что союз “и” в логике высказываний употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом “и” два высказывания, далёкие друг от друга по содержанию. В логике же высказываний рассматривается конъюнкция двух любых высказываний.

Определение 3. Дизъюнкцией двух высказываний a и b называется высказывание, обозначаемое символом aÚb, которое является истинным, если истинно хотя бы одно из высказываний a и b, и ложным, если оба они ложны. Читается: “a или b”. Высказывания a и b называются членами дизъюнкции.

Например, для высказываний “10>8” и “8=10” дизъюнкция “(10>8)Ú(8=10)” будет истинным высказыванием: “(10>8)Ú(8=10)”=1 (это высказывание записывают короче: “10³7”).

Таблица истинности дизъюнкции, выражающая зависимость логического значения дизъюнкции aÚb от логических значений её членов a и b имеет вид:

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

Упражнение 1.6. Определите значение истинности следующих высказываний:

а) Пермь расположена на Каме и 2×3=6.

б) 8 — простое число и 11 — простое число.

в) 8 — простое число или 11 — простое число.

г) Число 2 чётное или это число простое.

д) 4 £ 5, 4 ³ 5, 3×7 £ 21, 3×7 ³ 21.

е) 2×2=4 или подводные лодки бороздят Камское водохранилище.

ж) 2×2=4, и 2×2 £ 5, и 2×2 ³ 4.

Решение. а) Так как оба высказывания, к которым применяется операция конъюнкции, истинны, то согласно определения этой операции, их конъюнкция является истинным высказыванием.

Упражнение 1.7. Определите значения истинности высказываний a, b, c, d и e, если:

а) a&(2×2=4) — истинное высказывание,

б) cÚ (2×2=5) — истинное высказывание,

в) b&(2×2=4) — ложное высказывание,

г) dÚ (2×2=5) — ложное высказывание,

д) e& (2×2=5) — ложное высказывание.

Решение. а) Конъюнкция высказываний является истинным высказыванием лишь в случае, когда оба из входящих в конъюнкцию составляющих высказываний (членов конъюнкции) истинны. В нашем случае второе соcтавляющее высказывание “2×2=4” истинно, а конъюнкция двух высказываний истинна. Поэтому первое соcтавляющее высказывание а истинно.

Упражнение 1.8. Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения (а и b — действительные числа):

а) а×b¹0. г) =0. ж) |a|£6.

б) а×b=0. д) |a|=3. з) а²+b²¹0.

в) а²+b²=0. е) |a|<3. и) ¹0.

Решение. г) Произведение не равно нулю лишь в случае, когда оба сомножителя не равны нулю, т.е. (а¹0)&(b¹0).

Определение 4. Импликацией двух высказываний aиbназывается высказывание, обозначаемое символом a®b, которое считается ложным, если a истинно и bложно, и истинным при всех других логических значениях высказываний aиb. Высказывание a называется условием или посылкой, высказывание b — заключением или следствием импликации.Читается: “если a,то b”.

Импликация a®b читается также следующим образом: “из a следует b“, “a влечёт b“, “a достаточно для b“, “b необходимо для a“, “a имплицирует В“.

Таблица истинности импликации имеет вид:

Например, импликации: “если 2×2=5, то 3>5” и “если 2×2=4, то 9 делится на 3” обе истинны, так как у первой из них посылка ложна, а у второй истинно следствие. А импликация “если 2×2=4, то 3>5” ложна, так как посылка истинна, а следствие ложно.

Принятые в логике чтения импликации a®b неудобны в том отношении, что в обычной речи предложения “если a, то b“, “из a следует b“ и “a влечёт b“ имеют совсем иной смысл: они выражают, что между высказываниями a и b существует некоторая зависимость, в силу которой высказывание b как-то может быть выведено из высказывания a. С этой точки зрения предложение “Если 2×2=5, то Лондон — столица Франции” лишено смысла. Но в силу определения 4 оно имеет смысл в логике высказываний. Причём оно является истинным высказыванием, так как посылка ложна. Таким образом, согласно определения 4 можно рассматривать импликацию любых двух высказываний, даже если они не связаны между собой по содержанию, и истинность импликации определяется только логическими значениями её посылки и заключения.

Значение импликации для математических доказательств состоит в том, что из истинности импликации и её посылки мы делаем вывод об истинности её следствия .

Определение 5. Эквиваленцией двух высказываний a и b называется высказывание, обозначаемое символом a«b, которое является истинным, если оба высказывания a и b либо истинны, либо ложны, и ложным в остальных случаях. Читается: “a тогда и только тогда, когда b” или “a эквивалентна b“. Высказывания a и b называются членами эквиваленции.

Эквиваленция a«b читается также следующим образом: “если a, то b, и обратно”, или “a равносильно b“, или же “a необходимо и достаточно для b“.

Таблица истинности эквиваленции имеет вид:

Например, эквиваленция “DSPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда в DSPQ угол P равен углу Q“ истинна, так как оба её члена либо одновременно истинны, либо одновременно ложны, что известно из школьного курса геометрии.

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

Упражнение 1.9. Определите значения истинности следующих высказываний:

а) Если 12 делится на 6, то 12 делится на 3.

б) Если 11 делится на 6, то 11 делится на 3.

в) Если 15 делится на 6, то 15 делится на 3.

г) Если 15 делится на 3, то 15 делится на 6.

д) Если Саратов расположен на Каме, то белые медведи обитают в Африке.

е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3.

ж) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3.

и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4.

к) Тело массой m обладает потенциальной энергией mgh тогда и только тогда, когда оно находится нв высоте h над поверхностью земли.

Решение. а) Так как высказывание-посылка “12 делится на 6” истинно и высказывание-следствие “12 делится на 3” истинно, то и составное высказывание на основании определения импликации также истинно.

ж) Из определения эквивалентности видим, что высказывание вида Р«Q истинно, если логическое значение высказываний Р и Q совпадают, и ложно в противном случае. В данном примере оба высказывания, к которым применяется связка “тогда и только тогда”, ложны. Поэтому всё составное высказывание истинно.

Упражнение 1.10. Пусть через a обозначено высказывание “9 делится на 3”, а через b — высказывание “8 делится на 3”. Определите значения истинности следующих высказываний: а) a®b; б) b®a; в) Øa®b; г) Øa®b; д) Øa®Øb; е) Øb®Øa; ж) a®Øb; з) a®Øa; и) a«b; к) Øa«Øb; л) Øa«b; м) a«Øb.

Решение. е) Имеем a =1, b=0. Поэтому Ø0®Ø1 =1®0=1.

Упражнение 1.11. Определите значения истинности высказываний a, b, c и d в следующих предложениях, из которых первые два истинны, а последние два ложны:

а) Если 4 — чётное число, то a.

б) Если b, то 4 — нечётное число.

в) Если 4 — чётное число, то c.

г) Если d, то 4 — нечётное число.

Решение. а) Согласно определения при истинной посылке импликация истинна только в том случае, когда истинно заключение. В нашем случае посылка «4 — чётное число» истинна и истинна вся импликация. Значит, a - истинна.

Упражнение 1.12. Определите значения истинности высказываний a, b, c и d в следующих предложениях, из которых первые два истинны, а последние два ложны: а) a « (2<3); б) b « (2>3); в) c « (2<3); г) d « (2>3).

Упражнение 1.13. Пусть через a обозначено высказывание “Этот треугольник равнобедренный”, а через b — высказывание “Этот треугольник равносторонний”. Прочитайте следующие высказывания:

а) Øa&Øb; г) (aÚb)«a;

б) Ø(aÚb); д) Ø(aÚb)« Øb;

в) Øa®Øb; е) (a&Øb)® ØØa.

Решение. е) Если треугольник равнобедренный и неравносторонний, то неверно, что он неравнобедренный.

Упражнение 1.14. Следующие составные высказывания расчлените на простые и запишите символически, введя буквенные обозначения для простых их составляющих:

а) Если 18 делится на 2 и не делится на 3, то оно не делится на 6.

б) Произведение трёх чисел равно нулю тогда и только тогда, когда одно из них равно нулю.

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

г) Если в треугольнике медиана не является высотой и биссектрисой, то этот треугольник неравнобедренный и неравносторонний.

Решение. г) Выделим и следующим образом обозначим простейшие составляющие высказывания:

a: “В треугольнике медиана является высотой”;

b: “В треугольнике медиана является биссектрисой”;

c: “Этот треугольник равнобедренный”;

d: “Этот треугольник равносторонний”.

Тогда данное высказывание символически записывается так:

(Øa&Øb)®(Øc&Ød).

1.3. Дальнейшие логические операции над высказываниями. Наряду с введёнными выше основными логическими операциями рассматриваются также другие, не менее важные, операции. Это - следующие:

a|b - штрих Шеффера, a¯b - стрелка Пирса, - aÅbкольцевая сумма. Они определяются следующими таблицами истинностей:

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: