МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Московский государственный институт электроники и математики
(Технический университет)
Кафедра «Вычислительные
системы и сети»
Методические указания к самостоятельным (домашней и контрольной) работам по курсу
«Математическая логика и теория алгоритмов»
Москва 2004
Учебное издание
Математическая логика и теория алгоритмов
Составитель: доц., канд. тех. наук
Предназначены для выполнения контрольной и домашней работ в части логики и исчисления высказываний, нормальной формы формул, полных систем булевых функций и теоремы Поста, минимизации формул и логики предикатов студентами II (дневного) курса специальности 22.0101.
УДК 51
Математическая логика и теория алгоритмов: Метод. указания к самостоятельным (домашней и контрольной) работам/ Моск. Гос. ин-т электроники и математики; Сост. . М., 20с.
Ил. 3. Библиогр.: 1 назв.
ISBN
Домашняя работа по исчислению
высказываний и логике предикатов
При решении задач по исчислению высказываний (ИВ) можно пользоваться одной из двух систем аксиом ИВ (двумя сразу нельзя):
А1. А
(ВА) 
1. А(ВА)
А2. (А(ВС)) ((АВ) (АС)) 2. (АВ) ((А(ВС)) (АС))
А3. (
ВА) ((ВА) В) 3. А
ВА
4. АВВ
5. А(В(АВ))
6. А(А
В)
7. В(АВ)
8. (АС) ((ВС) ((АВ) С)
9. (АВ) ((АВ) А)
10. АА
При использовании системы аксиом вывод будет короче. Вывод в ИВ – это последовательность формул, где каждая формула или аксиома, или теорема, или гипотеза, или получена по правилу вывода. Правило вывода m. p.: Если в выводе есть две формулы вида АВ и А, то после них в выводе можно писать формулу В. Считается, что формула В получена по правилу m. p. из формул А и АВ. Правило записывается так: А, АВ
или А, АВ 
В. В
Выводом формулы А считается вывод, в котором формула А является последней. Если в выводе формулы А отсутствуют гипотезы, то формула А называется теоремой ИВ. Все аксиомы являются как бы схемами аксиом, в них вместо формул А, В и С можно корректно подставить любые формулы. Если формула А заменяется другой формулой, то сразу во всей аксиоме. В выводе можно применять теорему о дедукции ИВ: если Г, АВ, то Г АВ и два её следствия: 1. АВ, ВС АС. Построим вывод формулы АС. 1) АВ – гипотеза № 1; 2) ВС – гипотеза № 2; 3) А – гипотеза № 3; 4) В получена по m. p. из первого и третьего шагов (из 1) и 3) ); 5) С получена по m. p. из 2) и 4). Вывод формулы С имеет длину пять. В итоге получили: АВ, ВС, А С. Применяем теорему о дедукции ИВ, переносим формулу А вправо и получаем: АВ, ВС АС. Следствие 2: А(ВС), В АС. Вывод длиной 5: А(ВС); В; А; ВС; С. Четвёртый шаг получен по m. p. из первого и третьего шагов, а пятый – из второго и четвёртого. Получили А(ВС), В, А С, применяя дедукцию, получим второе следствие. Следствия можно считать ещё двумя правилами вывода. В правилах вывода тоже, как и в аксиомах, можно корректно одновременно во всём правиле вывода одну формулу заменять другой. Правило m. p. может быть записано и так: 
, 
.
При выводе можно использовать 7 теорем ИВ: Т1. АА.
Т2. АА. Т3. А(АВ). Т4. (ВА) (АВ). Т5. (АВ) (ВА). Т6. А (В(АВ)). Т7. (АВ) ((АВ) В). В теоремах ИВ, в том числе и в теореме о дедукции и её следствиях, формулы С, А и В так же могут быть корректно заменены другими.
Для примера получим ещё одно правило вывода: А, ВА В. В пятую теорему вместо формулы А поставим формулу В, а вместо В поставим А и получим: (ВА) (АВ). Теоремы и аксиомы можно вставлять в любое место вывода. Теперь вывод формулы В длиной 5: А; ВА; (ВА) (АВ); АВ; В. Четвёртый шаг вывода получен по m. p. из второго и третьего шагов, а пятый – из первого и четвёртого. Все три вновь полученные правила вывода можно применять, как и правило m. p., наряду с теоремой о дедукции.
Во втором задании по логике предикатов надо написать всё, что требуется в задании с использованием логики предикатов. Никакой дополнительной информации для выполнения задания не требуется, всё есть в самом задании. Например: на множестве натуральных чисел N имеется два трёхместных предиката: S
(x, y,z)=1 
x+y=z, P(x, y,z)=1 x*y=z (x, y, z 
N). Используя эти предикаты записать формулу с одной свободной переменной x, истинную тогда и только тогда, когда x делится на три. Ответ: F(x)=(
z)( S(z, z,y) 
S(z, y,x)). z+z=y и y+z=x, значит x=3
z. А можно и так: F(x)=(z) P(3,z, x) – это тоже правильно.
Теорема Ферма утверждает, что для любого целого n>2 не существует натуральных чисел x, y и z, удовлетворяющих равенству: x
+y=z.Этому равенству поставим в соответствие предикат R
(x, y,z, n) на множестве натуральных чисел, истинный тогда и только тогда, когда равенство выполняется. (n>2) запишем, используя предикаты предыдущего примера: (z) S(3,z, n). Теорему Ферма можно записать так: ((z) S(3,z, n)) R(x, y,z, n).
Варианты домашней работы
Ж. | Доказать, что следующие формулы выводимы в ИВ: а) | На множестве натуральных чисел N имеется два трёхместных предиката: S |
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул
При решении задач по логике высказываний не более половины вариантов можно выполнить с помощью таблицы истинности, а лучше везде применять логические способы. Для этого понадобятся основные равносильности:
1). АВ
ВА коммутативность
2). ААА идемпотентность
3). А(ВС)(АВ)С ассоциативность
4). АВВА коммутативность
5). ААА идемпотентность
6). А(ВС)(АВ)С ассоциативность
7) А (ВС)(АВ) (АС) дистрибутивность относительно
8) А (ВС)(АВ) (АС) дистрибутивность относительно
9). А(АВ)А первый закон поглощения
10). А(АВ)А второй закон поглощения
11). 
АА снятие двойного отрицания
12). (АВ)АВ первый закон Моргана
13). (АВ)АВ второй закон Моргана
14). А(АВ)(АВ) первая формула расщепления
15). А(АВ) (АВ) вторая формула расщепления
Следующие равносильности выражают одни логические символы через другие:
16). А~В(АВ) (ВА)(АВ) (АВ)
17). АВАВ(АВ)
18). АВАВ(АВ)
19). АВ(АВ) (А В)
Основные тавтологии, к которым сводятся тождественно истинные формулы с помощью равносильных преобразований:
1). АА
2). АА
3). А(ВА)
4). (АВ((ВС) (АС)) цепное рассуждение
5). (А(ВС)) ((АВ) (АС))
6). АВА; АВВ
7). А(В(АВ))
8). А(АВ); В(АВ)
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 |
