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



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


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ
Московский государственный институт электроники и математики

(Технический университет)

Кафедра «Вычислительные

  1. системы и сети»


  • Методические указания к самостоятельным (домашней и контрольной) работам по курсу


«Математическая логика и теория алгоритмов»

  • Москва 2008



  1. Учебное издание
  2. Математическая логика и теория алгоритмов



  1. Составитель: доц., канд. тех. наук Л.Е.Захарова



УДК 519.1

Предназначены для выполнения контрольной и домашней работ в части логики и исчисления высказываний, нормальной формы формул, полных систем булевых функций и теоремы Поста, минимизации формул и логики предикатов студентами II (дневного) курса специальности 22.0101.
Математическая логика и теория алгоритмов: Метод. указания к самостоятельным (домашней и контрольной) работам/ Моск. Гос. ин-т электроники и математики; Сост. Л.Е. Захарова. М., 2008. 23 с.

Ил. 1. Библиогр.: 3 назв.
ISBN 5-94506-100-х

Контрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул
При решении задач по логике высказываний не более половины вариантов можно выполнить с помощью таблицы истинности, а лучше везде применять логические способы. Для этого понадобятся основные равносильности:

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). А В); В В)

9). ( В А) (( В А) В)

10). ((А В) А) А закон Пирса

При доказательстве эквивалентностей или равносильностей надо либо правую формулу равносильными преобразованиями свести к левой, либо левую к правой, либо обе к какой-то одной, третьей формуле. Если требуется доказать тождественную истинность формулы, то её надо равносильными преобразованиями свести к вышеизложенным тождествам. Если заданий несколько, то не более половины можно выполнить с помощью таблицы истинности. Например, докажем девятую равносильность: А В) (А А) В) А В) А. Здесь использованы восьмая, вторая и десятая равносильности.

Логические символы и называют двойственными друг другу. Рассмотрим формулы, содержащие только эти логические символы и инверсию. Формула А двойственна формуле А, если она получена из А одновременной заменой и на двойственные.

Система булевых функций называется полной, если любая булева функция может быть выражена через функции системы с помощью суперпозиций. Например, система из трёх функций { , , } является полной. Если система функций полная и любая из функций этой системы может быть выражена с помощью суперпозиций через функции второй системы функций, то эта вторая система функций тоже является полной. В общем случае для проверки полноты системы функций надо составлять таблицу Поста. Она нужна для проверки теоремы Поста для этой системы: Если система полная, то для каждого из функционально замкнутых классов T , T , S, L и M найдётся функция из системы, не принадлежащая этому классу. Например, для системы { , , } таблица Поста имеет вид:


ФункцияT T SLM

++--+

++--+

--++-
Эта система функций является полной, так как в каждом столбце таблицы присутствует «-». Функция принадлежит T , если во всех нулях она равна нулю, и принадлежит T , если во всех единицах она равна единице. Функция f(x,y, … ,w) самодвойственна, если f(x,y, … ,w)= f( x, y, … , w). Функция линейна, если линеен её полином Жигалкина. Для инверсии полином Жигалкина имеет вид: x+1= x, он линеен и «+» - это сложение по модулю два. Для дизъюнкции: x y=xy+x+y, он не линеен и xy – это x y, это и есть нелинейность. Монотонная функции не должна упасть на возросшем наборе переменных. Набор переменных возрос, если все переменные или увеличились, или не изменились. Система функций независима, если ни какая функция из системы не может быть выражена с помощью суперпозиций через остальные функции системы. Система { , } независима, так как T , T , L, L. Система { , , } зависима, смотри выше законы Моргана.

xyzf

0000

0011

0100

0110

1001

1011

1101

1110
Формулу называют элементарной конъюнкцией, если она является конъюнкцией (может быть и одночленной) переменных и отрицаний переменных: x y, x y z. Формула находится в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией (может быть и одночленной) элементарных конъюнкций: (x y) ( x y z). Формула находится в Совершенной ДНФ (СДНФ), если каждый её дизъюнктивный член содержит по одному разу в прямом или инверсном виде все переменные формулы , и все её дизъюнктивные члены попарно различны: (x y z) (x y z) ( x y z). Аналогично определяются элементарная дизъюнкция, КНФ и СКНФ. Приводить формулы к их нормальным формам надо используя равносильные преобразования. Для приведения к совершенным формам можно использовать таблицы истинности формул: пусть f(x,y,z)=(x z) ( y z), СДНФ получается из единиц функции, а СКНФ – из нулей. При получении СДНФ нули переменных переходят в их инверсии: ( x y z) (x y z) (x y z) (x y z), здесь элементарные конъюнкции получены последовательно из наборов переменных (001), (100), (101) и (110). При получении СКНФ единицы переменных переходят в их инверсии.
Минимизация проводится в классе ДНФ методом минимизирующих карт. Функция должна быть задана её таблицей истинности или её СДНФ. Минимизирующая карта имеет 2 строк, где n – число переменных функции, и на единицу меньше столбцов. Например, для n=3:

x y z x y x z y z x y z x yz x y x z y z x y z xy z x y x zy z x y z xyz x y x zy z x y z x y zx yx z y zx y z x yzx yx z y zx y z xy zx yx zy zx y z xyzx yx zy zx y z

Использование карты основано на следующем: если какая то конъюнкция последнего столбца карты не входит в СДНФ функции, то все конъюнкции этой строки не входят ни в одну ДНФ функции. Возьмём функцию f(x,y,z)=(x z) ( y z) с таблицей истинности, представленной выше. Далее убираем из карты строки, соответствующие конъюнкциям, не вошедшим в СДНФ функции:

x yz x y x z y z x y z x y zx yx z y zx y z x yzx yx z y zx y z xy zx yx zy zx y zВычеркнутые в этих строках конъюнкции убираем во всех остальных строках карты. В каждой строке оставляем конъюнкции с наименьшим числом сомножителей:

y zx yx zx y y zx zВидно, что y z и x z обязательно войдут в ответ, так как они остались по одному в строке, они же составят результат.

  1. Варианты контрольной работы


1.Обосновать метод доказательства «разбором случаев»:



Привести пример такого доказательстваПостроить формулу от трёх переменных, которая принимает то же значение, что и большинство (меньшинство) переменных. Для четырёх переменных – большинство (меньшинство) и равное количество. 2.Доказать тождественную истинность формул:

По СКНФ формул А и В построить СКНФ и СДНФ формулы 3.Доказать, что: а) если (А В) и ( ) тождества, то и (С В) тождество; б) если (А В) и (А и (В Д) тождества,, то (С Д) тождество; в) если ( А В) и ( ) тождества, то и (А тождество;По СКНФ формул А и В построить СКНФ и СДНФ формулы А~В.4.При каких значениях переменных формула истинна: Построить формулу А такую, чтобы данная формула была тождеством: А)

Б) 5.При каких значениях переменных формулы истинны:

А) ;

Б) );

В) .Найти СКНФ и СДНФ

а)

б) 6.Доказать эквивалентности:

А) ;

Б) ;Привести к ДНФ и КНФ:

а)

б) К.Доказать, что если А В и А С тождества, то и В С тождество.Найти СДНФ и СКНФ: а) (а в с) а с) с с); б) (а в) ( а с); в) ( а в) в).Л.При каких значениях переменных формула истинна: ((А В) С) В)) ((А В) С) ?Привести к ДНФ и КНФ: а) (а в с) а с) с с); б) (а в) ( а с); в) ( а в) в).У.Доказать тождественную истинность формул: а) ( А В) А); б)(А В) ((С А) В)); в) ((А В) А) А; г) А В);По СДНФ формул А и В построить а) СКНФ и СДНФ формулы А В; б) СКНФ и СДНФ формулы А В;Ф.Доказать тождественную истинность формул: а) (P Q) (Q P)); б) (P Q) (P Q)); в) (P (Q (P Q))); г) ((P Q) ((Q R) (P R)));По СКНФ формул А и В построить а) СКНФ и СДНФ формулы А В; б) СКНФ и СДНФ формулы А В;Х.Доказать следующие равносильности: а) В) А В; б) (А В) С) Д) Д) Д) С); в) А С) С) В) С);Построить формулу от трёх переменных, истинную тогда и только тогда, когда ровно две переменных ложны. То же для четырёх переменных.Ч.При каких значениях переменных x, y, z, u, w, v следующие формулы ложны: а) (((x (y z)) ( y x)) y); б) (((x y) z) ((x y) (x z))); в) ((x y) (( x y) (x y)));Привести к ДНФ и КНФ: а) (А В) ( В С); б) ( В) А)); в) ( А В)~(В~С); г) ((А В) А)) ( В С);Ш.При каких значениях переменных x, y, z, u, w, v следующие формулы ложны: а) ((x y) (x z) (y z) (u v) (u w) (v w) ( x u)); б) (((x y) ((y z) (z x))) ((x y) z));Найти СДНФ: а) (А В) ( В С); б) ( В) А)); в) ( А В)~(В~С); г) ((А В) А)) ( В С);Щ.Доказать тождества: а) (а~в) (в~с) (а~с); б) (а~в)~((а в) а));Найти СКНФ: а) (А В) ( В С); б) ( В) А)); в) ( А В)~(В~С); г) ((А В) А)) ( В С);Z.При каких значениях переменных p,q,r следующие формулы ложны:

а) ((p q) (p (q p))); б) ( (p (q p)) (p r)); в) ((p (q p)) p); г) (((p q) q) (p q));Привести к ДНФ и КНФ: а) (( А В) ((В С) С))); б) (((А В) А) А))); в) ( ((А В) А) ((А В) В)).Q.При каких значениях переменных p,q,r следующие формулы истинны: а) ((p (q p)) (( q p) q)); б) (p q) ( p q); в) (((p q) (p r)) (p (q r)));По СКНФ формулы А построить а) СДНФ формулы А (двойственной к А); б) СКНФ и СДНФ формулы А;S.Найти СКНФ: а) (( А В) ((В С) С))); б) (((А В) А) А))); в) ( ((А В) А) ((А В) В)).Доказать, что совокупность функций, двойственных функциям из функционально замкнутого класса, образует функционально замкнутый класс.R.Найти СДНФ: а) (( А В) ((В С) С))); б) ((А В) А) А)); в) ( В) А) ((А В) В).Доказать, что пересечение двух функционально замкнутых классов есть функционально замкнутый класс.Г.Построить формулу от трёх переменных, истинную в том и только в том случая, когда большинство (меньшинство) переменных ложно. Для четырёх переменных – большинство (меньшинство) и равное количество.Доказать, что из всякой нелинейной функции и функций 0 и 1 можно получить суперпозициями функцию конъюнкции.Д.Построить формулу А такую, чтобы данная формула была тождественно-ложной: А)

;

Б) ;Доказать, что единственными полными системами из одной двуместной булевой функции являются системы, содержащии одна функцию Шеффера, а другая функцию Вебба (стрелку Пирса).Е.Построить формулу Q от переменных A, B, C так, чтобы

(было эквивалентно) и

Проверить полноту систем булевых функций: а) {+, ~}; б) {0, } ; в) { }; г) {~, , 0}. Будут ли эти системы функций независимыми.Ё.Привести к ДНФ и КНФ: а)

б) Проверить полноту систем функций: а) { , 0}; б) {+, , 1};

в) {~, }.Ж.Привести к ДНФ и КНФ: а)

и б)

Проверить полноту систем функций: а) { , 1}; б) {+, , 0};

в) { , }.З.Найти СДНФ и СКНФ: а)

б) Проверить полноту систем функций: а) { , 1}; б) {+, 0};

в) { , , }.И.Найти СДНФ и СКНФ: : а)

и б)

Доказать независимость систем функций: а) { , +}; б) { }, где x y = (y x).Й.Построить формулу Q от переменных A, B, C так, чтобы

и

были тождественно-ложными.Проверить полноту систем функций: а) { , 1}; б) {+, , 0};

в) { , }, где x y = (y x).Ъ.Построить формулу Q от переменных A, B, C так, чтобы а) (A Q)~(A B) и (A Q)~(A C) (было эквивалентно); б) (C Q)~(C (A B)) и (Q C)~( (A B) C);Методом минимизирующих карт найти минимальную ДНФ для

(x y z) (y t) ( x t) ( y t)Ы..По СДНФ формул А и В построить СКНФ и СДНФ формулы А~В.Привести пример полной системы функций, состоящей из одной трёхместной функции (f(x,y,z)).Ь.По СДНФ формул А и В построить СКНФ и СДНФ формулы Доказать, что число самодвойственных функций от n переменных равно 2 .Э.Найти СДНФ: а) (С А) ( С) А); б) ( ((А В) А) С))); в) ( С)) ((А В) С)).Составить релейно-контактные схемы для функций, считая x y= x y : а) ((x y) (y z)) (x z); б) (x y) ( x (y z));Ю.Привести к ДНФ и КНФ: а) (С А) ( С) А); б) ( ((А В) А) С))); в) ( С)) ((А В) С)).Составить релейно-контактные схемы для функций, считая x y= x y : а) (x y) (y z); б) (x (y z)) (y x).Я.Найти СДНФ: а) (С А) ( С) А); б) ( ((А В) А) С))); в) ( С)) ((А В) С)).Проверить полноту систем функций: а) {+, 1}; б) { , };

в) { , }.М.Проверить правильность следующего рассуждения. Если Джонс не встречал Смита этой ночью, то либо Смит был убийцей, либо Джонс лжёт (т.е. встречал). Если Смит не был убийцей, то Джонс не встречал Смита этой ночью и убийство имело место после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжёт. Значит Смит был убийцей. Выразить с помощью суперпозиций: а) через 1, +, ; б) , через , ; в) через 0, ; г) , , через ! (штрих Шеффера: а!в= а в); д) , через , ;Н.Доказать выполнимость формул a) (p p); б)(p q) (q p); в) (q (p r)) ((p r) q)Методом минимизирующих карт найти минимальную ДНФ для а) (x y) ( y z) (x z); б) (x y z) ( x y z);О.Доказать следующие эквивалентности: а) ((А В) С) А))~((А В) С) А)); б) ((А В) С) Д))~((А С) С) Д));Методом минимизирующих карт найти минимальную ДНФ для

( x y) (x y t) (y z t) П.Доказать следующие эквивалентности: а) (А В))~А; б) (А В))~А; в) (А А)~ А; г) (А В) В)~А;

Методом минимизирующих карт найти минимальную ДНФ для

(x y z) ( x y t) (y z t) (y z t) (x y z)Р.Доказать следующие эквивалентности: а) ((А В) ((А В) ( А В)))~(А В); б) (А ( А В))~(А В); в) (А В С))~А;Методом минимизирующих карт найти минимальную ДНФ для f(x,y,z), равной 1 только на оценках: <1, 1, 1>, <1, 0, 1>, <0, 0, 1>, <0, 0, 0>.С.Доказать тождественную истинность формул: а) (P (Q P)); б) (P P); в) ((P Q) ((P (Q R)) (P R))); г)((P Q) P); Методом минимизирующих карт найти минимальную ДНФ для а)

(x y z) ( x y) ( y z); б) (x y) (x y z)Т.Доказать тождественную истинность формул: а) ((P Q) Q); б) (P (P Q)); в)( Q P) (( Q P) Q);Методом минимизирующих карт найти минимальную ДНФ для

x ( x y) ( x y z) ( x y z t)Ц.Доказать следующие равносильности: а) А А А; б) (А В) С) Д) Д) Д) С); в)А ( А В) А В;Доказать, что число линейных функций от n переменных равно 2 .7.При каких значениях переменных формулы истинны: А) Б)

В) Доказать, что нельзя выразить с помощью суперпозиций: а) импликацию через инверсию и эквиваленцию; б) инверсию через импликацию.8.При каких значениях переменных формулы ложны: А)

Б) Представить многочленом Жигалкина импликацию и эквиваленцию.9.Пусть формула А не содержит никаких логических символов, кроме ~. Доказать, что А является тождественно-истинной тогда и только тогда, когда каждая переменная входит в А чётное число раз.Доказать, что из всякой несамодвойственной функции и функции инверсии можно получить суперпозициями функции 0 и 1.А.Пусть формула А не содержит никаких логических символов, кроме ~ и . Доказать, что А является тождеством тогда и только тогда, когда каждая переменная и символ входят в А чётное число раз.Доказать, что объединение функционально замкнутых классов может не быть функционально-замкнутым.Б.Доказать эквивалентность: Доказать, что следующие классы не являются функционально замкнутыми: а) класс функций от трёх переменных; б) класс функций, сохраняющих 0, но не сохраняющих 1.В.Записать составные высказывания в виде формул, употребляя высказывательные переменные для обозначения высказываний: а) Для того, чтобы x было нечётным, достаточно, чтобы оно было простым; б) если идёт дождь, то дует ветер; в) если дует ветер, то идёт дождь; г) ветер дует тогда и только тогда, когда идёт дождь; д) неверно, что ветер дует тогда и только тогда, когда нет дождя; е) Таня ходит в театр только тогда, когда там показывают пьесу из современной жизни.Доказать, что из всякой немонотонной функции и функций 0 и 1 можно получить суперпозициями функцию инверсии.J.При каких значениях переменных p,q,r следующие формулы истинны:

а) ( (p q) (p (q r))); б) ( (r (q p)) (p r)); в) ((r (q p)) p); г) (((p q) q) (r q));Построить две булевы функции от четырёх переменных А, В, С, Д, аналогичные функции Вебба ( А В) и штриху Шеффера ( А В). Доказать, что каждая из этих четырёхместных функций будет полной системой.G.При каких значениях переменных p,q,r следующие формулы ложны: а) ((p (q r)) (( q p) r)); б) (p q) ( r q); в) (((r q) (p r)) (p (q r)));Доказать, что для класса всех булевых функций базисами являются функция Вебба ( А В) и штрих Шеффера ( А В). Выразить через них все функции полной системы { , , }.


  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