Лекции - Дискретная математика - файл glava1-1.DOC

Лекции - Дискретная математика
скачать (4918.8 kb.)
Доступные файлы (14):
glava1-1.DOC852kb.16.04.2003 02:03скачать
glava1-2.DOC626kb.16.04.2003 02:03скачать
glava1-4.DOC773kb.16.04.2003 02:03скачать
glava1-5.DOC1080kb.16.04.2003 02:03скачать
glava1-6.DOC483kb.16.04.2003 02:03скачать
glava2-1.DOC495kb.16.04.2003 02:03скачать
glava2-2.DOC851kb.16.04.2003 02:03скачать
glava2-3.DOC701kb.16.04.2003 02:03скачать
glava2-4.DOC477kb.16.04.2003 02:03скачать
glava2-5.DOC618kb.16.04.2003 02:03скачать
glava3-1.DOC2380kb.16.04.2003 02:03скачать
glava3-5.DOC1511kb.16.04.2003 02:03скачать
glava3-7.DOC625kb.16.04.2003 02:03скачать
glava4-1.DOC763kb.16.04.2003 02:03скачать

glava1-1.DOC

Предисловие


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

В МИЭТ дискретную математику изучают студенты нескольких групп факультета МПиТК, а также факультетов ЭКТ, ИМЭ.

Данная книга соответствует курсу дискретной математики, читаемому в 4-м семестре студентам факультета МПиТК, и написана на основе опыта преподавания авторами этого предмета. Авторы считают, что ее использование в полном или частичном виде возможно и на других факультетах.

Книга содержит элементы математической логики (алгебру высказываний, высказывания с кванторами, предикаты), теорию булевых функций, теорию графов (включая потоки в сетях), автоматов, а также машины Тьюринга и рекурсивных функций. Не включены комбинаторика и теория кодирования. Комбинаторика изучается студентами факультета МПиТК в 5-м семестре в курсе теории вероятностей, а теория кодирования – в курсах лекций, читаемых кафедрой ИПОВС.

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

ГЛАВА 1. Элементы алгебры высказываний и булевой алгебры

§1.1. Высказывания


Высказыванием называется некоторое повествовательное утверждение, про которое можно однозначно сказать, истинно оно или ложно. Например, {число 50 делится на 10} – истина; {50 больше 100} – ложь.

Всякое высказывание является либо истинным, либо ложным (закон исключения третьего).

Никакое высказывание не может быть одновременно истинным и ложным (закон противоречия).

Отрицанием высказывания (обозначается  или ) называется высказывание, утверждающее, что высказывание не выполняется. Отрицание высказывания можно получить, сказав: “утверждение не имеет места” или “ не выполняется”. Определяющим словом здесь является частица “НЕ”.

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

Высказывание ) (или ) называется двойным отрицанием высказывания . Имеет место равенство ) = (закон двойного отрицания).

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

Примеры предикатов. Пусть , , делится на 4}, {любой -угольник можно разрезать на треугольники}. Здесь истинно, ложно, ложно, истинно, истинно, не имеет смысла.

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

противном случае ложно.

Таблица истинности для предиката

















Ложь

Л

Истина

Л

Л

И

Л



Аналогично предикатам от одной переменной определяются предикаты от нескольких переменных: , и т.д.

Для предиката можно построить высказывания “” и “” (читается: “для любого имеет место ” и “существует такое , что имеет место ”). Первое из них считается истинным в том и только том случае, когда верно при всех , второе – когда верно хотя бы при одном . Символы “” и “” называются квантором всеобщности и квантором существования соответственно. Квантор всеобщности заменяется в словесных формулировках словами всякий, каждый, любой, все. Квантор существования заменяется в словесных формулировках словами существует, найдется, какой-нибудь, хотя бы один.

С помощью кванторов можно образовывать также новые предикаты: если – предикат, то, например,

– предикат от ,

– высказывание.

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

;

.

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

(1) – истинно,

(2) – ложно.

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

Отрицания высказываний “” и “”.

Имеет место равенство . Действительно, утверждение “неверно, что для всех ” – это то же самое, что “для какого-нибудь не ”. Аналогично справедливо равенство , так как утверждение “неверно, что существует , для которого ” равносильно следующему: “для всех не ”. Таким образом, чтобы построить отрицание высказывания, содержащего кванторы, надо кванторы заменить на , а на , а утверждение, стоящее под знаком кванторов, заменить на противоположное.

Пример.

.

Операции над высказываниями


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

1. Дизъюнкцией (или логической суммой) двух высказываний и называется высказывание (обозначается ), истинное в случае, если хотя бы одно из высказываний и истинно. Дизъюнкция читается “ или” и соответствует союзу “ИЛИ”.

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

3. Эквиваленцией двух высказываний и называется высказывание (обозначается или ), истинное тогда и только тогда, когда оба высказывания и одновременно истинны или ложны. Читается “ эквивалентно” и выражается словом “ЭКВИВА-ЛЕНТНО”.

4. Импликацией двух высказываний и называется высказывание (обозначается или , или ; называется посылкой, заключением), ложное в том и только том случае, когда посылка истинна, а заключение ложно. Читается “из следует”, соответствует слову “СЛЕДУЕТ”.

Символы, обозначающие логические операции, называются логическими связками.

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

Таблица истинности логических операций.




















И

И

И

И

И

И

И

Л

И

Л

И

Л

Л

Л

Л

И

Л

И

И

Л

Л

И




Л

Л

Л

Л

И

И




Из таблицы истинности для импликации видно, что если посылка и импликация истинны, то истинно и заключение. В этом случае пишут и говорят, что из следует . Если же из следует , а из следует , то высказывания и называют равносильными и обозначают .

Два высказывания равносильны, если их таблицы истинности совпадают. Например, высказывания и равносильны. Убедимся в этом, построив их таблицы истинности:









И

И

И

И

И

Л

Л

Л

Л

И

И

И

Л

Л

И

И

С помощью введенных операций из элементарных высказываний строятся сложные высказывания, например:

.

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

Тождественно истинные высказывания – высказывания истинные всегда, независимо от того, истинны или ложны составляющие их высказывания. Тождественно истинное высказывание иначе называют тавтологией. Тождественно ложные высказывания – высказывания ложные всегда, независимо от истинности или ложности составляющих их высказываний. Тождественно ложное высказывание иначе называют противоречием. Тождественно истинные и тождественно ложные высказывания обозначаются буквами (true) и (false) (по-русски: И и Л) соответственно (или цифрами 1 и 0).

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

Свойства операций над высказываниями


1. а) (коммутативность дизъюнкции);

б) (коммутативность конъюнкции);

2. а) (ассоциативность дизъюнкции);

б) (ассоциативность конъюнкции);

3. а) (дистрибутивность дизъюнкции относительно конъюнкции);

б) (дистрибутивность конъюнкции относительно дизъюнкции);

4. и законы де Моргана.

5. ; ; ;

6. (или ) (закон исключенного третьего);

(или (закон противоречия);

7. (или ); (или );

(или ); (или ).

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

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

Пример. Однажды следователю пришлось одновременно допрашивать трех свидетелей: Клода, Жака и Дика. Их показания противоречили друг другу, и каждый из них обвинял кого-нибудь во лжи. Клод утверждал, что Жак лжет, Жак обвинял во лжи Дика, а Дик уговаривал следователя не верить ни Клоду, ни Жаку. Но следователь быстро вывел их на чистую воду, не задав им ни одного вопроса. Кто из свидетелей говорил правду?

Решение. Рассмотрим высказывания: {Клод говорит правду}; {Жак говорит правду}; {Дик говорит правду}.

Нам не известно, какие из них верны, но известно следующее:

1) либо Клод сказал правду, и тогда Жак солгал, либо Клод солгал, и тогда Жак сказал правду;

2) либо Жак сказал правду, и тогда Дик солгал, либо Жак солгал, и тогда Дик сказал правду;

3) либо Дик сказал правду, и тогда Клод и Жак солгали, либо Дик солгал, и тогда неверно, что оба других свидетеля солгали (т.е. хотя бы один из этих свидетелей сказал правду).

Выразим эти высказывания в виде системы уравнений:



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







.

Но в том и только том случае, если , а . Следовательно, Жак говорит правду, а Клод и Дик лгут.

Любая -членная операция, обозначаемая, например, , будет полностью определена, если установлено, при каких значениях высказываний результат будет истинным или ложным. Один из способов задания такой операции – заполнение таблицы значений:











И

И



И

И или Л











Л

Л



Л

И или Л

В таблице значений высказывания, образованного от простейших высказываний , имеется строк. Столбец значений имеет также позиций. Следовательно, имеется различных вариантов его заполнения, и, соответственно, число всех -членных операций равно . При число одночленных операций равно 4, при число двучленных – 16, при количество трехчленных – 256 и т.д.

Рассмотрим некоторые специальные виды формул.

Формулу называют элементарной конъюнкцией, если она является конъюнкцией переменных и отрицаний переменных. Например, формулы , , , – элементарные конъюнкции.

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

Теорема 1 (о приведении к д. н. ф. ). Для любой формулы можно найти равносильную ей формулу , являющуюся д. н. ф. .

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

Формулу называют элементарной дизъюнкцией, если она является дизъюнкцией переменных и отрицаний переменных. Например, формулы , , и т.д.

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

Теорема 2 (о приведении к к. н. ф.). Для любой формулы можно найти равносильную ей формулу , являющуюся к. н. ф.

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


Рассмотрим произвольную -членную операцию , заданную своей таблицы значений, не являющуюся противоречием. Рассмотрим строки таблицы, в которых принимает значения “И”. Для каждой строки составим элементарные конъюнкции из множителей, где -й множитель равен (в этой строке принимает значение “И”) или (в этой строке принимает значение “Л”). Далее возьмем дизъюнкцию всех полученных конъюнкций. В итоге получится формула (д. н. ф. ), задающая операцию, равносильную . Действительно, каждая из построенных конъюнкций будет истинна только при тех значениях истинности высказываний , которые стоят в соответствующей строчке. Поскольку была взята дизъюнкция по всем наборам значений истинности высказываний , на которых истинна, то построенное высказывание истинно на всех этих наборах и только на них. На остальных наборах оно ложно.

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

Аналогично, рассматривая строки, в которых операция , не являющаяся тавтологией, принимает значения “Л”, и составляя конъюнкцию (число множителей равно числу отмеченных строк таблицы) дизъюнкций из слагаемых, где -е слагаемое равно (в этой строке принимает значение “Л”) или (в этой строке принимает значение “И”). В итоге получится формула, задающая операцию, равносильную . Построенная формула называется совершенной конъюнктивной нормальной формой (СКНФ) операции .

Пример. Построить СДНФ и СКНФ операции, заданной таблицей истинности.









И

И

И

Л

И

И

Л

И

И

Л

И

Л

И

Л

Л

И

Л

И

И

Л

Л

И

Л

Л

Л

Л

И

Л

Л

Л

Л

И

Решение. Операция принимает значение “И” только на трех наборах, а “Л” на пяти наборах. Соответственно,

СДНФ=;

СКНФ=

.

Теорема 3. Любая логическая операция может быть выражена через операции отрицания и конъюнкции.

Доказательство. Выразим дизъюнкцию через операции отрицания и конъюнкции, используя закон двойного отрицания и закон де Моргана: .

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

Теоремы


Теоремы в математике чаще всего формулируются в виде «», где – условие теоремы (то, что дано), а – заключение (то, что утверждается). и являются высказываниями (возможно, неопределенными).

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

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

Теоремы и называются обратными друг другу. Первую называют прямой теоремой, другую – обратной.

Приведем пример.

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

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

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

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

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

Например, теорема, противоположная теореме Пифагора, может быть сформулирована так: если треугольник не прямоугольный, то квадрат любой его стороны не равен сумме квадратов двух других сторон.

Метод доказательства от противного. Ранее было отмечено, что высказывания и равносильны. Поэтому иногда для доказательства теоремы предполагают истинным высказывание и пытаются вывести отсюда справедливость высказывания . Если это удается (т.е. будет доказана теорема ), то исходную теорему тоже можно будет считать доказанной.

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

Правильные рассуждения


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

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

Распространенными схемами правильных рассуждений являются следующие схемы: .

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

Перечислим наиболее важные тавтологии ( произвольные формулы):

1. (закон исключения третьего);

2. ; 3. ;

4. (цепное рассуждение);

5. ;

6. ; 7. ;

8. ; 9 ;

10. (закон Пирса).

Задачи для самостоятельного решения


1. Среди следующих предложений выделить те, которые являются высказываниями и установить, истинны они или ложны:

а) число очень мало ;

б) существует ли в произвольном треугольнике точка равноудаленная от его сторон?

в) около всякого выпуклого четырехугольника можно описать окружность;

г) существуют внеземные цивилизации;

д) каждое целое число является и числом рациональным;

е) для произвольных множеств и верно, что ;

ж) ; з) ; и) ;

к) сумма углов треугольника равна .

2. Для каких натуральных чисел предикат истинен:

а) ; б) ?

3. Для каких действительных предикат {числа являются сторонами некоторого треугольника} истинен?

4. Записать с помощью кванторов следующие высказывания и указать, если это возможно, какие из этих высказываний истинны, а какие ложны:

а) сумма любых двух натуральных чисел больше первого слагаемого;

б) полугруппа имеет левую единицу;

в) некоторое кратное любого натурального числа делится на сумму двух заданных натуральных чисел;

г) любой элемент полугруппы делится слева и справа на квадрат самого себя;

д) квадрат любого натурального числа делится на 3 или на 5;

е) каждый элемент имеет не более двух левых делителей.

5. Записать символически следующие высказывания, включив в кванторы указание множества значений переменных:

а) в множестве натуральных чисел есть наименьшее;

б) в множестве натуральных чисел нет наибольшего;

в) любые два рациональных числа либо равны друг другу, либо одно из них больше другого.

6. Сформулировать отрицание следующих высказываний:

а) Все люди хорошие.

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

в) В каждом учебном округе г. Москвы есть школа, в которой есть класс, все ученики которого любят ходить в походы.

7. Построить отрицание высказываний:

а) ; б) ;

в) ;

г) .

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

9. По мишени произведено три выстрела. Что означает следующее высказывание, записанное в символической форме ({мишень поражена при -м выстреле},):

a) ; б) ; в) ;

г) ?

10. Построить таблицы истинности для следующих формул:

а) ; б) ;

в) ; г) ;

д) .

11. Какие из высказываний должны быть истинными и какие ложны, чтобы высказывание было истинным?

12. Доказать свойства операций 1-7 (стр. 9).

13. Выразить (т.е. найти равносильные формулы) эквиваленцию и импликацию через дизъюнкцию, конъюнкцию и отрицание.

14. Выразить основные операции через

а) конъюнкцию и отрицание; б) дизъюнкцию и отрицание;

в) импликацию и отрицание.

15. Выразить дизъюнкцию через импликацию.

16. На вопрос, кто из трех студентов изучал логику, был получен правильный ответ: если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий. Кто из студентов изучал логику?

17. Определить, кто из четырех студентов сдал экзамен, если известно, что:

1) если первый сдал, то и второй сдал;

2) если второй сдал, то третий сдал или первый не сдал;

3) если четвертый не сдал, то первый сдал, а третий не сдал;

4) если четвертый сдал, то и первый сдал.

18. Назовем операциями Шеффера следующие операции:

.

Выразить через них отрицание, дизъюнкцию и конъюнкцию.

19. Найти СДНФ и СКНФ импликации и эквивалентности.

20. Построить формулу от трех переменных, которая:

а) принимает истинное значение тогда и только тогда, когда ровно две переменные ложны;

б) принимает такое же значение, как и ее большинство переменных.

21. Один логик попал в плен к дикарям и был заключен в темницу, имеющую два выхода. Вождь дикарей предложил пленнику следующий шанс на спасение: “Один выход ведет на свободу, а другой на верную смерть. Ты можешь избрать любой. Сделать выбор тебе поможет мой стражник. Он останется здесь, чтобы ответить на один твой вопрос – любой, какой ты пожелаешь ему задать. Но я предупреждаю тебя: если у этого стражника хорошее настроение, то он говорит правду, если же у него настроение плохое, то он лжет!” После минутного размышления сообразительный логик задал один вопрос, после чего безошибочно выбрал тот выход, который вел на свободу. Что это был за вопрос?

22. В уставе одного клуба записаны следующие правила: 1) финансовый комитет должен быть избран из состава общего комитета; 2) никто не может быть одновременно членом и общего, и библиотечного комитетов, если он не входит при этом в финансовый комитет; 3) никто из членов библиотечного комитета не может быть в финансовом комитете. Упростите эти правила.

23. Брауну, Джонcу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники были на синем «Бьюике»; Джонс сказал, что это был черный «Крайслер», а Смит утверждал, что это был «Форд Мустанг» и ни в коем случае не синий. Стало известно, что, желая запутать следствие, каждый из них правильно указал либо только марку машины, либо ее цвет. Какого цвета был автомобиль и какой марки?

24. На вопрос, кто из трех учащихся изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй. Кто из учащихся изучал логику?

25. Разбирается дело Иванова, Петрова и Сидорова. Один из них совершил преступление. На следствии каждый из них сделал два заявления. Иванов: «Я не делал этого. Сидоров сделал это». Петров: «Сидоров не виновен. Иванов сделал это». Сидоров: «Я не делал этого. Петров не делал этого». Суд установил, что один из них солгал дважды, другой – дважды сказал правду, третий – один раз солгал, один раз сказал правду. Кто совершил преступление?

26. Доказать приведенные выше тавтологии 1-10.

27. В каждом из пунктов сформулировать теорему и обратную к ней теорему; укажите, в каких случаях обратная теорема верна:

а) {четырехугольник является ромбом }, {диагонали четырехугольника делят его углы пополам};

б) {натуральное число делится на 9}, {сумма цифр числа делится на 3}.

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

а) Если четырехугольник – параллелограмм, то его диагонали делят друг друга пополам.

б) Если сумма цифр десятичной записи натурального числа делится на 5, то это число делится на 5.

в) Если прямая параллельна прямой , а прямая параллельна прямой , то прямая параллельна прямой .

29. Являются ли правильными следующие рассуждения?

а) Если число простое, то оно нечетное. Число 5 нечетное. Следовательно оно простое.

б) Если человек занимается спортом, то он никогда не болеет. Петр занимается спортом. Следовательно, Петр никогда не болеет.

в) Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжет. Следовательно Смит был убийцей.

30. Пусть формула не содержит никаких логических символов, кроме. Доказать, что является тождественно истинной тогда и только тогда, когда каждая переменная входит в четное число раз.

31. Пусть формула не содержит никаких логических символов, кроме и ¬. Доказать, что является тождественно истинной тогда и только тогда, когда каждая переменная и символ ¬ входят в нее четное число раз.

Ответы


1. а) Не является; б) не является; в) ложно; г) не является; д) истинно; е) истинно; ж) не является; з) не является; и) ложно; к) считается истинным в геометрии Евклида и ложным в геометрии Лобачевского.

2. а) ; б) . 3. 4. а) истинно; б) ; в) истинно; г) ; д) ложно; е) . 5. а) ; б) ; в) . 6. а) Существует хотя бы один плохой человек.

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

в) Существует учебный округ такой, что во всех его школах и всех классах есть хотя бы один ученик, который не любит ходить в походы. 7. а) ; б) ;

в) ; г) . 8. 8. 9. а) мишень поражена по крайней мере одним выстрелом; б) все выстрелы поразили мишень; в) из первых двух выстрелов хотя бы один не поразил мишень, а третий поразил мишень; г) мишень поражена одним и только одним выстрелом. 11. Высказывание тождественно истинно. 13. , . 14. а) ; б) , в) .

15. . 16. Второй студент. 17. Все сдали. 18. ; . 19. СДНФ: , СКНФ: , . 20. а) ;

б) . 21. “Верно ли, что первый выход ведет на свободу и у тебя сейчас хорошее настроение или первый выход ведет к смерти и у тебя сейчас плохое настроение?” Указание. Построить СДНФ искомого высказывания. 22. 1) Финансовый комитет должен быть избран из состава общего; 2) никто из библиотечного комитета не должен входить в общий. 23. Черный «Бьюик». 24. Третий учащийся изучал логику. 25. Сидоров. 29. а) нет; б) да; в) нет.



Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации