уч.пос
.2.pdf11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
Задача №15.Проанализируйте следующее рассуждение на предмет его правильности. Для этого выявите логическую схему, на которой оно основано, и выясните, справедливо ли оно.
а) справедливо;
б) не справедливо.
1.Некоторые люди взошли на Эверест. Эдмунд Хиллари - человек.
Следовательно, Эдмунд Хиллари взошел на Эверест.
71
2.Во всех городах за Полярным кругом бывают белые ночи. Петер-
бург не находится за Полярным кругом. Следовательно, в Петербур-
ге не бывает белых ночей.
3.Все сильные шахматисты знают теорию шахматной игры. Иванов не является сильным шахматистом. Следовательно, Иванов не знает теорию шахматной игры.
4.Некоторые змеи ядовиты. Ужи - змеи. Следовательно.ужиядовиты.
5.Всякий металл является твердым веществом. Ртуть не твердое ве-
щество. Следовательно, ртуть не металл.
6.Все рациональные числа - действительные. Все целые числа - ра-
циональные. Следовательно, все целые числа – действительные.
7.Ни одно действительное число не является мнимым числом. Все целые числа – действительные. Следовательно, ни одно целое число не есть мнимое.
8.Все целые числа – рациональные. Некоторые вещественные числа – целые. Следовательно, некоторые вещественные числа - рациональ-
ные.
9.Все ромбы – параллелограммы. Все прямоугольники - параллело-
граммы. Следовательно, все ромбы – прямоугольники.
10.Все ромбы – параллелограммы. Все прямоугольники - параллело-
граммы. Следовательно, все прямоугольники – ромбы.
72
11.Некоторые четные функции – периодические. Ни одна монотонная функция не является четной. Следовательно, ни одна периодическая функция не монотонна.
12.Некоторые четные функции – периодические. Ни одна монотонная функция не является четной. Следовательно, ни одна монотонная функция не является периодической.
13.Все квадраты – правильные многоугольники. Ни одна трапеция не есть правильный многоугольник. Следовательно, ни одна трапеция не есть квадрат.
14.Некоторые математики суть логики. Все логики знакомы с произве-
дениями Аристотеля. Следовательно, некоторые математики знако-
мы с произведениями Аристотеля.
15.Все студенты БГУ – жители Башкортостана. Некоторые жители Башкортостана – пенсионеры. Следовательно, некоторые студенты БГУ – пенсионеры.
16.Все хирурги – врачи. Некоторые врачи – Герои России. Следова-
тельно, некоторые хирурги – Герои России.
17.Все пловцы – спортсмены. Ни один спортсмен не курит. Следова-
тельно, ни один курящий не является пловцом.
18.Все литераторы –гуманитарии. Некоторые гуманитарии – бывшие студенты БГУ. Следовательно, некоторые литераторы – бывшие студенты БГУ.
73
19.У всех млекопитающих сердце состоит из четырех камер. Дельфин
– млекопитающее. Следовательно, сердце дельфина состоит из че-
тырех камер.
20.Всякий металл электропроводен. Натрий – металл. Следовательно,
натрий электропроводен.
21.Каждый гражданин России должен признать ее конституцию. Все депутаты России – граждане России. Следовательно, каждый из де-
путатов должен признать конституцию Россию.
22.Все натуральные числа – целые. Некоторые рациональные числа – натуральные. Все рациональные числа – действительные. Следова-
тельно, некоторые действительные числа – целые.
23.Во всех городах миллионниках есть трамваи. Белорецк не является городом миллионником. Следовательно, в Белорецке нет трамваев.
24.Все математики знают английский язык. Некоторые люди, знающие английский язык, знают французский язык. Следовательно, некото-
рые математики знают французский язык.
74
5. Типовые варианты контрольных работ.
Контрольная работа №1. ВАРИАНТ 1
1.Составить таблицу истинности для формулы
2.Эквивалентны ли формулы
и ?
3.Упростить формулу
4.Записать формулу в СКНФ и СДНФ
5.Записать формулу в приведенном виде (содержащем только опе-
рации , , над простыми переменными)
6.Определить, является ли форма тавтологией, противоречием или ни тем и ни другим
7.Записать данную форму, используя только связки
a),
b),
c)
75
ВАРИАНТ 2.
1.Составить таблицу истинности для формулы
2.Эквивалентны ли формулы и ?
3.Упростить формулу
.
4.Записать формулу в СКНФ и СДНФ
.
5.Записать формулу в приведенном виде (содержащем только опера-
ции , , над простыми переменными)
.
6.Определить, является ли форма тавтологией, противоречием или ни тем и ни другим
.
7.Записать данную форму, используя только связки
a),
b),
c)
.
76
Контрольная работа №2.
ВАРИАНТ 1.
1.Построить полином Жегалкина для функции
(x |
y) ( x (x |
y)) . |
2.Проверить принадлежность функции функционально замкнутым классам
(x3 x2 ) x1 x3 .
3.Проверить принадлежность функции, заданной столбцом значений,
функционально замкнутым классам
11100111.
4.Проверить полноту системы булевых функций, используя теорему Поста:
x1 x2 x1 x3 x2 x3 , x1 , x1 |
x2 . |
5. Является ли данная система булевых функций базисом?
{ , , 0} .
6.На скольких наборах значений аргументов принимает значение 0
следующая булева функция:
.
77
ВАРИАНТ 2.
1.Построить полином Жегалкина для функции
|
|
|
|
|
|
(x |
y) (x y) (x |
y) . |
2.Проверить принадлежность функции функционально замкнутым классам
(x | y) |
x z . |
3.Проверить принадлежность функции, заданной столбцом значений,
функционально замкнутым классам
11000110.
4.Проверить полноту системы булевых функций, используя теорему Поста:
x1 x2 , x1 |
x1 x3 . |
5. Является ли данная система булевых функций базисом?
{ , , 0,1}.
6.На скольких наборах значений аргументов принимает значение 0
следующая булева функция:
.
78
Контрольная работа №3.
ВАРИАНТ 1.
1.Какими могут быть множества истинности предикатов P(x) и Q(x),
заданных над непустым множеством М, если известно, что следую-
щее высказывание истинно:
2.Является ли следующая формула выполнимой:.
3.Докажите, что следующие формулы не равносильны:
и
4.Является ли следующая формула тавтологией логики предикатов:
ВАРИАНТ 2.
1.Какими могут быть множества истинности предикатов P(x) и Q(x),
заданных над непустым множеством М, если известно, что следую-
щее высказывание ложно:
2.Является ли следующая формула выполнимой:
.
3.Докажите, что следующие формулы не равносильны:
и
4.Является ли следующая формула тавтологией логики предикатов:
79
СПИСОК ЛИТЕРАТУРЫ
1. Юлмухаметов Р.С., Исаев К.П., Трунов К.В.Дискретная математика.
Уфа: РИО БашГУ, 2005.
2. Игошин В.И. Задачи и упражнения по математической логике и тео-
рии алгоритмов. М.: Изд-ий центр «Академия», 2007.
3. Мендельсон Э. Введение в математическую логику. Пер. с англ. М.:
Наука, 1977.
4. Новиков Ф.А. Дискретная математика для программистов. СПб.: Пи-
тер, 2000.
5.Яблонский С.В. Введение в дискретную математику. М.: Наука. Глав.
изд-во ф.-м. лит., 1986.
80