Упражнения

1.1) Составить РКС, предварительно упростив формулу

2) Упростить РКС

3) Упростить РКС

4 ) Упростить РКС

5) Упростить РКС

2. Для ниже приведенных формул составить логические схемы:

1) 2) 3) .

3. Для ниже приведенных схем составить формулу, упростить её и по упрощенной формуле составить новую схему:

1)

2 )

3)

4)

Вопросы для самоконтроля

1. Дайте определение высказывания, приведите примеры истинных и ложных высказываний.

2. Запишите таблицу истинности для инверсии, конъюнкции, дизъюнкции, импликации и эквиваленции.

3. Дайте определение тождественно истинной, тождественно ложной и равносильным формулам.

4. Как распределены приоритеты между логическими операциями?

5. Как определяется название сложной формулы?

6. Каков порядок составления таблицы истинности для сложной формулы?

7. Запишите аксиомы и законы алгебры логики.

8. В чем суть полноты систем логических операций?

9. Поясните правила склеивания для элементарных конъюнкций и дизъюнкций. Приведите примеры.

10. Поясните правила поглощения для элементарных конъюнкций и дизъюнкций. Приведите примеры.

11. Поясните правила развертывания для элементарных конъюнкций и дизъюнкций. Приведите примеры.

12. Что такое НДФ, СНДФ, НКФ и СНКФ?

13. Каков вид общей записи любой логической функции в СНДФ?

14. Как записать по таблице истинности логическую функцию в СНДФ? Приведите пример.

15. Каков вид общей записи любой логической функции в СНКФ?

16. Как записать по таблице истинности логическую функцию в СНКФ? Приведите пример.

17. Как осуществляется переход от произвольно заданной логической функции к СНДФ? Приведите пример.

18. Как осуществляется переход от произвольно заданной логической функции к СНКФ? Приведите пример.

19. Перечислите и поясните основные этапы минимизации логических функций, исходя из СНДФ и СНКФ.

20. Расскажите, как осуществляется минимизация логических функций расчетным методом.

21. Как определяется размер карты Карно для общего случая числа переменных в логической функции?

22. Как заполняются клетки карты Карно?

23. Как осуществляется нумерация строки столбцов карты Карно?

24. Каково правило включения клеток карты Карно в покрытие?

25. Как определяется импликанта для каждого покрытия?

26. Поясните суть минимизации логических функций методом Квайна.

27. Поясните, какова связь между логическими функциями и РКС?

28. Поясните, какова связь между логическими функциями и цифровыми логическими семами?

29. Как строятся цифровые схемы по формулам алгебры логики?

2. Исчисление высказываний

Исчислением называют составную часть некоторых разделов математики, трактующих правила вычислений и оперирования с объектами того или иного типа. Например, говорят о дифференциальном, интегральном, вариационном и т.д. исчислениях.

В исчислении высказываний объектами исследований являются высказывания. Их исчисление служит для формализации способов логических рассуждений, в которых учитывается лишь логическая структура высказываний, а именно: как одни высказывания получены из других с помощью таких логических операций, как отрицание, конъюнкция дизъюнкция и импликация. Обратим внимание, что сюда не входит операция эквиваленции. В одних литературных источниках данную операцию в этот список включают, в других – нет (например, в математической энциклопедии эта операция в список не включена).

В алгебре логики (высказываний) мы под термином “высказывание” понимали любое повествовательное предложение, о котором можно было сказать, истинно оно или ложно. При этом мы испытывали затруднения, когда вставал вопрос о том, считать ли некоторое повествовательное предложение высказыванием, если о его истинности или ложности нельзя было сказать ничего определенного. Поэтому очевидно, что для построения логической теории, которая позволяла бы формализовать процесс получения одних высказываний из других, пользоваться понятиями истинности и ложности нет необходимости. Исчисление высказываний, как раздел математической логики, построено таким образом, что в нем не используются понятия истинности и ложности и не применяются сами законы алгебры логики.

Оно является аксиоматической системой. А в основе любой аксиоматической системы лежит совокупность аксиом, с помощью которых, а также определенных правил вывода, получаются новые знания, в частности теоремы.

Возникает вопрос, что такое теорема? Еще со средней школы мы усвоили, что под теоремой понимается всякое утверждение, в истинности которого убеждаются при помощи доказательства. Но теперь встает очередной вопрос: а что такое доказательство? Ответив на этот вопрос, мы ответим и на первый.

В современной математике под доказательством понимают конечную последовательность высказываний каждое из которых является либо аксиомой, либо выводится из одного или более предыдущих высказываний этой последовательности по логическим правилам.

Отсюда теоремой, или доказуемым высказыванием, называется высказывание, являющееся последним высказыванием некоторого доказательства.

Принято считать, что аксиома – это некоторое исходное положение, принимаемое в данной науке без доказательства. Или об аксиоме говорят, что это самоочевидная истина, не требующая доказательства. При таком взгляде на аксиому считается, что её истинность подтверждается многочисленными опытами и практикой. Однако в математической логике считается, что аксиома – это все-таки теорема, причем ее доказательство состоит из одного шага.