64821-матлогика-3
.doc
Контрольная работа
По математической логике и теории алгоритмов
Вариант 3
Задание к контрольной работе № 1
Исследовать на равносильность формулы f1, f2 и f3, заданные в дизъюнктивной нормальной форме, двумя способами:
1) путем их представления (на основе равносильных формул алгебры логики) в виде совершенных конъюнктивных нормальных форм с подтверждением правильности реструктуризации исходных формул построением их таблиц истинности;
2) путем представления заданных формул f1, f2 и f3 в виде полиномов Жегалкина, формируемых двояко: а) на основе формулы Жегалкина; б) на основе метода неопределенных коэффициентов.
По варианту 3:
f1=
;
f2=
;
f3=
.
Решение
1. Приведение заданных функций к СКНФ.
а) f1=
;
Применим свойство
дистрибутивности дизъюнкции относительно
конъюнкции, т.е. разложим выражение по
первому слагаемому
:
по свойству
поглощения:
,
тогда
- СКНФ.
Составим таблицу истинности.
Сначала вычислим
СДНФ f1=
,
затем
.
|
x |
y |
z |
|
xz |
|
f1 |
|
|
|
f1 |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Равенство последних двух столбцов подтверждают правильность расчетов.
б) f2=
- СКНФ
Составим таблицу истинности:
|
x |
y |
z |
|
|
|
|
f2 |
|
|
f2 |
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
в) f3=
.
- СКНФ
Заметим, что
.
2. а) на основе формул Жегалкина:
Выбираем пары
одинаковых выражений, используем
свойство
:
Таким образом,
.
Таким образом,
.
б) на основе метода неопределенных коэффициентов.
-
Из таблицы истинности для
следует:
Убираем нулевые слагаемые:
Подставляем в
уравнения
:
Подставляем
,
и
в остальные уравнения:
=>
Из последнего уравнения:
Таким образом, получили:
;
;
;
;
;
;
;
.
Значит,
-
Из таблицы истинности для
следует:
Убираем нулевые слагаемые:
Подставляем в
уравнения
:
Подставляем
,
и
в остальные уравнения:
=>
Из последнего уравнения:
Таким образом, получили:
;
;
;
;
;
;
;
.
Значит,
Ответ:
СКНФ и СДНФ:
;
;
.
Или в форме полиномов:
;
;
.
Задание к контрольной работе № 2. Часть 1.
1) Методом от противного выяснить, верно ли предложенное логическое следование. Справедливость полученного вывода подтвердить решением этой же задачи на основе определения понятия логического следования.
2) Найти все не равносильные между собой и не тождественно истинные формулы алгебры высказываний, являющиеся логическими следствиями заданных формул-посылок F1, F2,….
3) Найти все не равносильные между собой и не тождественно ложные формулы алгебры высказываний, для которых заданная формула G является логическим следствием.
По варианту 3:
-
Установить, верно ли логическое следование
-
Найти все следствия из указанных посылок
.
-
-
Решение
1)
.
Предположим, что данное следование не выполняется, то есть
.
Данное выражение
верно только в случае
,
откуда следует
.
Второе выражение
системы выполняется, если
и
.
Подставим данные значения в первое уравнение:
Значит,
Из условия
следует, что
;
из условия
следует, что
.
Таким образом, мы пришли к противоречию.
Значит, логическое следование
истинно.
2) Найти все следствия из указанных посылок
.
Сначала составим таблицу истинности для данного выражения:
|
X |
Y |
|
|
|
|
0 |
0 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
0 |
- СДНФ.
СКНФ:
Следствиями из этой формулы будут следующие выражения:
-
Дизъюнктивные одночлены:
,
,
.
-
Конъюнкции из двух одночленов:
(по
свойству поглощения)
-
Конъюнкция из трех одночленов:
Ответ: следствиями
из посылки
будут следующие выражения:
,
,
,
,
,
,
.
Задание к контрольной работе № 2. Часть 2.
4) Построить релейно-контактную схему, заданную формулой А, и определить ее функцию проводимости; провести минимизацию схемы.
5) Вывести формулу для указанного ряда Sn и обосновать ее справедливость методом математической индукции.
По варианту 3:
4) Функция проводимости:
.
5)
.
Решение:
4)
Релейно-контактная
схема, заданная формулой
имеет вид:
Таблица истинности для данной схемы:
|
x |
y |
z |
YZ |
|
|
|
|
|
|
|
F |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
Таким образом, функция проводимости построенной РКС описывается дискретным образом в следующем виде:
.
Минимальная РКС:
.
Значит, минимальная релейно-контактная схема будет иметь вид
5)
Имея в виду, что операция суммирования является дискретным вариантом операции интегрирования, а
представляет собой
некоторый многочлен степени 5, то и
результатом суммирования
будет
некоторый многочлен пятой степени; его
коэффициенты можно найти методом
неопределенных коэффициентов:
.
n=1: A + B + C + D + E + F = 1
n=2: 32A + 16B + 8C + 4D + 2E + F = 17
n=3: 243A + 81B + 27C + 9D + 3E + F = 98
n=4: 1024A + 512B + 64C + 16D + 4E + F =610