Москва 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=3z. А можно и так: 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(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу с одной свободной переменной x, истинную тогда и только тогда, когда а) x=0; б) x=1; в) x=2; г) x чётно; д) x нечётно; е) x - простое число.
Ё.	Доказать, что если в ИВ выводима формула В [(А, … , АВ], то формула ((А … А)В) тождественно истинна.	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу с двумя свободными переменными x и y, истинную тогда и только тогда, когда а) x=y; б) x<=y; в) x<y; г) x делит y; д) x и y - простые числа.
Ж.	Доказать, что следующие формулы выводимы в ИВ: а) (АА); б) (АА).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу с тремя свободными переменными x, y и z, истинную тогда и только тогда, когда а) z – наименьшее общее кратное x и y; б) z – наибольший общий делитель x и y; в) z=max(x, y); г) z =min(x, y).
З.	Вывести в ИВ: а) (А (ВС)), (АВ), А С; б) (АВ), В А; в) А, В (АВ).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую а) коммутативность сложения; б) ассоциативность сложения; в) коммутативность умножения; г) ассоциативность умножения; д) дистрибутивность сложения относительно умножения.
И.	Доказать для ИВ: а) Г, (А В) А (удаление ); б) Г, А А (удаление ).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую а) бесконечность множества простых чисел (нет max и min); б) то, что всякое число есть сумма четырёх квадратов; в) наименьших общих кратных и наибольших общих делителей для чисел, отличных от нуля.
Й.	Доказать для ИВ: а) Г, (А В) В (удаление ); б) Г, А С, Г, В С Г, (А В) С (удаление ).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую а) не существование единицы; б) конечность множества простых чисел; в) то, что всякое число можно представить в виде суммы двух квадратов; г) то, что для всякого числа существует строго меньшее число; д) существование наибольшего натурального числа. Истинны ли эти формулы?
К.	Доказать для ИВ: а) Г, А (В А) (введение ); б) Г, А В, Г, А В Г А (введение ).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую а) то, что всякое чётное число, большее двух, есть сумма двух простых; б) то, что для всякого числа существует строго большее число; в) то, что для всякого числа существует бесконечное множество строго больших его чисел.
Л.	Вывести: а) ((АА) А); б) АА;	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую, что уравнение 3+2+1=0 имеет в точности два различных корня.
М.	Доказать для ИВ: а) Г, В (В А) (введение ); б) Г, В, А (В А) (введение).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую, что система уравнений не имеет решения.
Н.	Доказать, что следующие правила допустимы: а) В, В, Г А В, Г А б) Г, А, В, Г С Г, В, А, Г С	Пусть М – множество точек, прямых и плоскостей с предикатами: Т(х)=1 х – точка, Пр(х)=1 х – прямая, Пл(х)=1 х – плоскость, Л(х, у) =1 х лежит на у. С использованием этих предикатов записать формулы: а) через каждые две точки можно провести прямую; если эти точки различны, то такая прямая единственна; б) через каждые три точки, не лежащие на одной прямой, можно провести единственную плоскость; в) определение параллельных прямых; г) определение параллельных плоскостей.
О.	Вывести: а) В (АВ); б) (АВ) (ВА); в) (АВ) (ВА).	Пусть М – множество точек, прямых и плоскостей с предикатами: Т(х)=1 х – точка, Пр(х)=1 х – прямая, Пл(х)=1 х – плоскость, Л(х, у) =1 х лежит на у. С использованием этих предикатов записать формулы: а) две прямые могут или не иметь общих точек, или иметь одну общую точку, или совпадать; б) Две плоскости не могут иметь конечное множество общих точек, а только бесконечное; в) две плоскости могут или не иметь общих прямых, или иметь одну общую прямую, или совпадать
П.	Выводимы ли в ИВ формулы: а) ((АВ) (АС)); б) (АВ) (ВА)?	Для двуместного предиката R(x, y) записать, что он (предикат) а) рефлексивен; б) симметричен; в) транзитивен; г) R(x, y) - отношение эквивалентности.
Р.	Выводимы ли в ИВ формулы: а) (((АВ) В) В); б) ( (АА) (АА)).	Пусть М=Р(А) – множество-степень (множество всех подмножеств) некоторого множества А. Двуместный предикат Q(x, y)=1 xy. Записать, что а) x = yz; б) x = yz; в) x – пустое множество; г) x=A; д) x есть дополнение A.
С.	Выводом из каких множеств формул Г является следующая последовательность: ((АВ) (ВА)), (АВ), (ВА), В, А	Пусть М=Р(А) – множество-степень (множество всех подмножеств) некоторого множества А. Трёхместный предикат f(x, y,z)=1 xy=z. Трёхместный предикат g(x, y,z)=1 xy=z. Двуместный предикат = - предикат равенства двух подмножеств x и y. Используя эти три предиката, записать, что а) xy; б) x есть одноэлементное множество.
Т.	Выводом из каких множеств формул Г является следующая последовательность: (А (ВС)), А, (ВС), В, С.	Для двуместного предиката R(x, y) записать, что он (предикат) а) рефлексивен; б) антисимметричен; в) транзитивен; г) R(x, y) - отношение нестрогого порядка.
У.	Вывести: а) (АА); б) ((АВ) (ВА)).	Для двуместного предиката R(x, y) записать, что он (предикат) а) антирефлексивен; б) антисимметричен; в) транзитивен; г) R(x, y) - отношение строгого порядка.
Ф.	Является ли выводом в ИВ: (А (АВ)), ((А (АВ)) (В (А (АВ)))), (В (А (АВ))).	На множестве натуральных чисел N имеется два одноместных предиката: g(x)=x+1, а P - произвольный одноместный предикат. Кроме того, имеется 0 (нуль). Использую всё вышеизложенное, записать аксиому индукции для P.
Х.	Являются ли выводами в ИВ: а) (А (АВ)); б) (А (ВА)), ((А (ВА)) В), В?	Выбрать предикаты и записать: а) аксиомы полугруппы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества; б) коммутативной полугруппы; в) моноида – полугруппы с единицей.
Ц.	Вывести: а) (АВ), (ВС) (АС); б) (А (ВС)) (В (АС)); в) (А (ВС)) ((АВ) С).	Выбрать предикаты и записать: а) аксиомы группы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества, наличие единицы и обратного элемента для каждого элемента из группы; б) абелевой (коммутативной) группы; в) циклической группы.
Ч.	Вывести: а) (АВ) ((АС) (ВС)); б) (АВ) (СА) (СВ); в) А (АВ) .	Выполнимы ли следующие формулы: а) x P(x); б) x P(x); в) x y (Q(x, x) Q(x, y)); г) x y (P(x) P(y)); д) x y (Q(x, y) z R(x, y,z)); е) (P(x) y P(y))?
Ш.	Вывести: а) (АВ) ((СА) (СВ)); б) (АВ) ((АС) (ВС)); в) А (АВ).	Являются ли тождественно-истинными следующие формулы: а) (x P(x) x P(x)); б) (x P(x) x P(x)); в) (x y Q(x, y) y x Q(x, y)); г) (x y Q(x, y) y x Q(x, y))?
Щ.	Вывести: а) ((АВ) С) (А (ВС)); б) (АВ) ((ВС) (АС)); в) (АВ) ((СА) (СВ)).	Доказать тождественную истинность следующих формул: а) (x (A(x) (BC(x))) (x( A(x) C(x)) B)), где x не свободна в B; б) (x(A(x) B(x)) (x A(x) B(x))).
Ы.	Вывести: а) (АВ) (ВА); б) (АВ) (ВА).	Доказать тождественную истинность следующих формул: а) ( x P(x) x P(x)); б) (x(A(x) B(x)) (x B(x) A(x))).
Ъ.	Доказать, что следующие правила допустимы в ИВ: а) Г А ; Г,А В Г, Г В (сечение) б) ((А … А)В) А, …, А В (удаление и ).	Выбрать предикаты и записать три аксиомы расстояний: 1) d(a, b)>=0 и d(a, b)=0 тогда и только тогда, когда a=b. 2) d(a, b)=d(b, a). 3) d(a, b)+d(b, c)>=d(a, c) (неравенство треугольника). d(a, b) = расстояние от a до b.
Ь.	Доказать, что следующие правила допустимы в ИВ: а) Г, (АВ) С Г, А, В С (расщепление посылок) б) Г С ; С, Г В Г, Г В.	Выполнимы ли следующие формулы: а) x y (P(x) P(y)); б) x yz (P(x) (Q(y) R(z))); в) yx (P(x) P(y)) ?
Э.	Доказать, что следующие правила допустимы в ИВ: а) Г С В, Г С б) (разбор случаев) ; Г, А С ; Г, В С Г, (А В) С	Пусть М=Р(А) – множество-степень (множество всех подмножеств) некоторого множества А. Двуместный предикат Q(x, y)=1 xy. Записать, что а) x = y+z (симметрическая разность x и y); б) x = y \ z (разность x и y); в) x – одноэлементное подмножество.
Ю.	Доказать, что следующие правила допустимы в ИВ: а) Г, А В Г, В А (контрапозиция) б) Г, А С Г, С А (доказательство от противного).	Выбрать предикаты и записать теорему Поста: для того, чтобы система булевых функций {f, … , f},была полной, необходимо и достаточно, чтобы для каждого из классов T, T, S, L и M нашлась функция f из системы, не принадлежащая этому классу.
Я.	Доказать, что следующие правила допустимы в ИВ: а) Г, А, В С Г, (АВ) С (объединение посылок) б) А, …, А В ((А … А)В) (введение и ).	Выбрать предикаты и записать: а) аксиомы кольца: множества с двумя бинарными операциями - + и . Относительно операции + кольцо является коммутативной группой, относительно операции - полугруппой. В кольце дистрибутивность: (а+в)с=ас+вс, с(а+в)=са+св. Аксиомы группы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества, наличие единицы и обратного элемента для каждого элемента из группы; Аксиомы полугруппы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества;
Б.	Доказать, что если существует вывод пустого множества: А, …, А , то формула (А … А) тождественно истинна.	Выбрать предикаты и записать: а) аксиомы кольца с единицей: множества с двумя бинарными операциями - + и . Относительно операции + кольцо является коммутативной группой, относительно операции - моноидом (полугруппой с единицей). В кольце дистрибутивность: (а+в)с=ас+вс, с(а+в)=са+св. Аксиомы группы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества, наличие единицы и обратного элемента для каждого элемента из группы; Аксиомы полугруппы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества;
В.	Доказать, что если формула В выводима ( В) , то формула В тождественно истинна.	Выбрать предикаты и записать теорему Лагранжа: порядок конечной группы делится на порядок своей подгруппы. Аксиомы группы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества, наличие единицы и обратного элемента для каждого элемента из группы;
Г.	Доказать, что каждая тождественно истинная формула А выводима в ИВ ( А) .	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую а) то, что два числа x и y взаимно просты (не имеют общих делителей); б) то, что два числа x и y имеют хотя бы один общий делитель; в) все три числа x, y и z стоят в ряду натуральных чисел подряд: или x, y, z или y, z,x и т. д. (6 вариантов).
Д.	Доказать, что следующее правило допустимо в ИВ: Г(А В); Г, АС; Г,ВС Г, Г, Г, С (удаление ).	На множестве натуральных чисел N имеется два трёхместных предиката: S(x, y,z)=1 x+y=z, P(x, y,z)=1 x*y=z (x, y, z N). Используя эти предикаты записать формулу, выражающую а) то, что число x является степенью числа 2; б) то, что число x не является степенью никакого числа; в) то, что из трёх чисел x, y и z какие-то два совпадают.
Е.	Доказать, что следующие правила допустимы в ИВ: а) Г, А Г, А (введение ); б) Г, А Г, А (удаление ).	Выбрать предикаты и записать теорему Кэли: всякая конечная группа порядка n изоморфна некоторой подгруппе симметрической группы S (группы подстановок). Подстановка – это биекция множества самого в себя. Аксиомы группы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества, наличие единицы и обратного элемента для каждого элемента из группы;