Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул



страница3/3
Дата02.01.2013
Размер0.68 Mb.
ТипКонтрольная работа
1   2   3
Варианты домашней работы



А.Выводимы ли в ИВ формулы:

(((а в) в) а); а а) ?На множестве натуральных чисел 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
Ж.Доказать, что следующие формулы выводимы в ИВ: а) А); б) (А А).На множестве натуральных чисел 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 x y. Записать, что а) x = y z; б) x = y z; в) x – пустое множество; г) x=A; д) x есть дополнение A.С.Выводом из каких множеств формул Г является следующая последовательность: ((А В) ( В А)), (А В), ( В А), В, АПусть М=Р(А) – множество-степень (множество всех подмножеств) некоторого множества А. Трёхместный предикат f (x,y,z)=1 x y=z. Трёхместный предикат g (x,y,z)=1 x y=z. Двуместный предикат = - предикат равенства двух подмножеств x и y. Используя эти три предиката, записать, что а) x y; б) 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) (B C(x))) (( x)( A(x) C(x)) B)), где x не свободна в B; б) (( x)(A(x) B(x)) (( x) A(x) ( x) B(x))).

Ы.Вывести: а) ( А В) ( В А); б) ( А В) А).Доказать тождественную истинность следующих формул: а) ( ( x) P(x) ( x) P(x)); б) (() x)(A(x) B(x)) (( x) B(x) ( 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)( y)( z) (P(x) (Q(y) R(z))); в) ( y)( x) (P(x) P(y)) ?Э.Доказать, что следующие правила допустимы в ИВ: а)

Г С

В, Г С

б) (разбор случаев) ;

Г, А С ; Г, В С

Г, (А В) С Пусть М=Р(А) – множество-степень (множество всех подмножеств) некоторого множества А. Двуместный предикат Q (x,y)=1 x y. Записать, что а) 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 (группы подстановок). Подстановка – это биекция множества самого в себя. Аксиомы группы: существование ассоциативной бинарной операции на множестве, не выводящей из этого множества, наличие единицы и обратного элемента для каждого элемента из группы;

Докажем теорему ИВ (А B) (B A), т.е. получим B) (B A). 1) А A (доказанная выше теорема ИВ); 2) A (B A) ( 1); 3) (B A) ((А B) (B A)) ( 7); 4) A ((А B) (B A)) (силлогизм 2) и 3)); 5) A (A B) (T3); 6) (A B) ((А B) (B A)) ( 6); 7) A ((А B) (B A)) (силлогизм 5) и 6)); 8) (А С) (( A С) ((А A) С)) ( 8, где C=(А B) (B A)); 9) ( A С) ((А A) С) (m.p. 4) и 8)); 10) (А A) С (m.p. 7) и 9)); 11) С=(А B) (B A) (m.p. 1) и 10)).

Получим вывод из гипотезы: (А B) C) (B C). Вывод: 1) А B (гипотеза); 2) (А (B С)) ((C (B С)) ((А C) (B С))) ( 8); 3) В (B С) ( 6); 4) A (B С) (силлогизм 1) и 3)); 5) (C (B С)) ((А C) (B С)) ((m.p. 4) и 2)); 6) C (B С) ( 7); 7) (А C) (B C) (m.p. 5) и 6)).

  1. Литература




  1. Новиков Ф.А. Дискретная математика для программистов – С.-П.:Питер, 2002

  2. Нефедов В.Н., Осипова В.А. Курс дискретной математики – М.: Изд-во МАИ, 1992

  3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера – М.: Энергоатомиздат, 1988


1   2   3

Похожие:

Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconНормальные формы формул логики предикатов
При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной...
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул icon5. 11. Как упростить логическую формулу?
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для...
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconКонтрольная работа «Электрический ток»
По какой из приведенных ниже формул можно рассчитать тепловую мощность тока на внешнем участке цепи?
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconРабота с текстовым процессором ms word: набор формул, создание списка иллюстраций, перекрестных ссылок, элементов автозамены и автотекста
Создайте новый документ, введите текст "Создание формул" и сохраните документ в своей папке под именем Формула doc
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconПодбор формул по графику. Линия тренда Подбор формул со многими неизвестными Расчет стоимости недвижимости Оценка эффективности рекламы Подбор формул по графику. Линия тренда
По ним с определенной мерой близости пытаются восстановить эмпирическую формулу (уравнение), которая может быть использована для...
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconКонтрольная работа по теме «Электростатика»
По какой из приведенных ниже формул можно рассчитать в си модуль напряженности электростатического поля точечного заряда q, находящегося...
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconВопросы вступительного экзамена в аспирантуру по специальности 01. 01. 06 – математическая логика, алгебра и теория чисел
Истинностные значения формул, равносильность, равносильные преобразования формул. Представление истинностных функций формулами
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул icon§ Определение доказуемой (выводимой) формулы
Следующим этапом в построении исчисления высказываний является выделение класса доказуемых (выводимых) формул
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул icon«Технология графических материалов» 3 курс 6 семестр (озо) Контрольная работа
Контрольная работа проходит в форме теста с использованием компьютерных технологий. В форме слайд-шоу студентам предлагается некоторое...
Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул iconЛогические операции над предикатами
Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org