Признаки равносильности формул

Основные булёвы операции

□ - Комментарии, упражнения, метаобозначения, числовые множества, совокупности;

□ – Дизъюнкция, конъюнкция, отрицание, импликация (следование), эквивалентность (равнозначность);

Законы (тавтологии) определяющие свойства введённых логических операций

□ - Идемпотентность, коммутативность, ассоциативность, дистрибутивность

(дизъюнкции и конъюнкции);

□ - Размещения, перестановки, сочетания, инверсии, мультимножества;

Какие из следующих четырёх теорем верны?

Т₁. Если каждое из натуральных чисел делится на 7, то и их сумма делится на 7.

Т₂. Если сумма двух чисел делится на 7, то каждое слагаемое делится на 7.

Т₃. Если сумма двух чисел не делится на 7, то ни одно из слагаемых не делится на 7.

Т₄. Если сумма двух чисел не делится на 7, то хотя бы одно из слагаемых не делится на 7.

 

Признаки равносильности формул

□ - Две формулы А и В алгебры высказываний равносильны тогда и только тогда, когда каждая их них является логическим следствием другой.

□ - Две формулы А и В алгебры высказываний равносильны тогда и только тогда, когда формула А ⇔ В - тавтология. (⇔ - равносильность высказывательных форм).

□ - Пусть А – формула, тогда Ā – тоже формула. Свободные и связанные переманные формулы Ā – это соответственно свободные и связанные переменные формулы А.

□ - Пусть А и С - формулы, причём нет таких предметных переменных, которые были бы связаны в одной формуле и свободны в другой.

 

Тест к модулю 2 [ Свойства конъюнкции, дизъюнкции и отрицания]

1. В определения внести соответствующие названия операций над сложными высказываниями [ отрицание (не), дизъюнкция (строгая (либо) и нестрогая (или), конъюнкция (и), импликация (если … то), эквиваленция (тогда и только тогда) ]

…………… высказываний А и В называется высказывание А ↔ В, которое истинно тогда и только тогда, когда либо истинны, либо ложны одновременно оба высказывания;

……………. высказываний А и В называется высказывание А → В, которое ложно тогда и только тогда, когда из истины следует ложь;

……………. высказываний А и В называется высказывание А ⊂ В, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний;

……………. высказываний А и В называется высказывание АВ, которое истинно тогда и только тогда, когда истинны оба высказывания;

.................. нестрогой или соединительной высказываний А и В называется высказывание А ⋁ В, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний;

…………… или инверсией, высказывания А называется высказывание Ā, которое истинно, когда высказывание А ложно, и ложно, когда А истинно.

2. Операции логики изобразить кругами Эйлера

- отрицание, инверсия

- нестрогаядизъюнкция (соединительная)

 

- строгая дизъюнкция (разделительная)

 

- конъюнкция

- импликация (следование)

 

- тождественность, равносильность, эквиваленция.

Тест к модулю 3 [ ДНФ, СДНФ, КНФ, СКНФ]

1. Внести соответствующие названияформул - дизъюнктивная нормальная форма (ДНФ) или конъюнктивная нормальная форма (КНФ):

- АВС ∨ АВ ∨ СВ ∨ С

 - (А ∨ В ∨ С) (А ∨ С) В

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

- Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных сумм (дизъюнктивных одночленов), называется КНФ данной формулы.

2. Тождественно истинная формула не имеет

 - СДНФ

 - СКНФ

3. Тождественно ложная формула не имеет

 - СДНФ

 - СКНФ

4. Внести соответствующие названия свойств СДНФ (1) или СКНФ (2):

 - ни одно слагаемое не содержит одновременно двух одинаковых сомножителей;

 - ни один из сомножителей не содержит двух одинаковых слагаемых;

 - ни одно слагаемое не содержит одновременно некоторое высказывание и его отрицание;

 - ни один из сомножителей не содержит одновременно некоторое переменное высказывание и его отрицание.

 

 

Тест к модулю 4 [ Полиномы Жегалкина]

1. С помощью конъюнкции и суммы по модулю два (М2 или строгой дизъюнкции) любую логическую функцию можно единственным образом представить в виде:

 - многочлена;

 - полинома Жегалкина;

 - логики предикатов;

 - математических понятий.

1. Если функцию xy будем искать в виде многочлена с неопределёнными коэффициентами: xy = a ⊕ bx ⊕ cy ⊕ dxy, является или нет итоговое уравнение xy = x ⊕ xy полиномом Жегалкина:

 - да;

 - нет.

1. Какая из предложенных операций не является константой?

 - x ⊕ x = 0

 - x ⊕ 1= x

 - у ⊕ ӯ = 0

 - x ⊕ 0= x

1. Для суммы М2 справедлива или нет формул

__________

у ₁ ⊕ у ₂ = ӯ ₁⊕ у ₂ = у ₁ ⊕ ӯ ₂

 - нет

 - да

Тест к модулю 5 [ ЭЛЕМЕНТЫТЕОРИИ ГРАФОВ]

1. Покажите, что всякий связный граф с m имеет не менее m - 1 рёбер.
2. На какие графы накладываются требования – а) направление каждой дуги должно совпадать с направлением пути; б) ни одно ребро не должно встречаться дважды:

 - не ориентированный граф;

 - орграф.

1. Какие матрицы связаны с неориентированными и ориентированными графами?

В чём их сходство? В чём состоит различие?

 

1. Матрицы смежности и матрицы инцидентности, привести примеры.
2. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

0 1 0 1 0 1

1 0 1 1 0 1

0 1 0 1 0 1

1 1 1 1 1 0

0 0 1 0 0 1

1 1 1 1 1 0

1. При задании графа матричным способом известны условия

b_ij = 1, если вершина V_i является началом дуги X_j,

b_ij = 0, если вершина V_i не инцидентна дуге X_j,

b_ij = -1, если вершина V_i является концом дуги X_j,.

Отметить к какой матрице (инцидентности или смежности) относится набор условий

 - матрица инцидентности не ориентированного графа;

 - матрица инцидентности ориентированного графа;

 - матрица смежности не ориентированного графа;

 - матрица смежности ориентированного графа;

Тест к модулю 6 [ Матрицы и графы. Способы задания графов]

1. При задании графа матричным способом известны условия

_{M [ ij ]} = 1, если вершина V_i смежна вершине X_j,

_{M [ ij ]} = 0, если вершина V_j не смежны.

Отметить к какой матрице (инцидентности или смежности) относится набор условий

 - матрица инцидентности не ориентированного графа;

 - матрица инцидентности ориентированного графа;

 - матрица смежности не ориентированного графа;

 - матрица смежности ориентированного графа;

1. Построить орграф по матрице инциденций

│ -1 0 0 1 0 │

D: │ 1 -1 0 0 -1 │

│ 0 1 1 1 0 │

│ 0 0 -1 -1 1 │

 

Тест к модулю 7 [ Деревья и их простейшие свойства]

1. Привести пример изображения деревьев в программировании (структура вложенности каталогов в современных операционных системах [ПК] является упорядоченным ориентированным деревом).

 

1. Конкретное применение деревьев в программировании:

 - деревья сортировки;

 

 - деревья упорядочивания;

 

 - бинарные деревья;

 

 - свободные деревья;

 

 - выровненные и полные деревья.

 

Тест к модулю 8 [Сети, потоки в сетях. Сетевые модели представления информации.]

1. К какому типу графов относится определение – Если каждому ребру графа поставлено в соответствие некоторое число (вес) –

 - ориентированный граф;

 

 - взвешенный или сеть;

 

 - не ориентированный граф.

 

Тест к модулю 9 [Комбинаторика.]

1. Раздел математики, занимающийся подсчётами количества различных комбинаций между объектами называется -

 - отношения;

 - изоморфизм;

 - комбинаторика.

1. К чему сводятся все комбинаторные задачи –

 - к подсчёту мощности конечных множеств и их отображений;

 - к практическому сравнению множеств;

 - к композициям функций.

1. Внести соответствующие названия соответственно 1) P_n = n!;

2) A_n^m = n!/ (n-m)!; 3) C_n^m = n !/ m!(n-m)!;

 - сочетания без повторений;

 - перестановки;

 - размещения без повторений.

1. Практическое применение комбинаторного анализа –

 - для геометрической интерпретации свойств булевых функций;

 - для аппарата алгебры высказываний;

 - в программировании при вычислениях дискретных конечных математических структур.

 

Тест к модулю 10 [Булёва алгебра]

1. Внести названия соответствующим следующим симметрическим функциям

1) f (x,y) = x ∧ y; 2) f (x,y) = x ⋁ y; 3) f (x,y) = (x ≡ y); 4) f (x,y) = x ⊕ y –

 - строгая дизъюнкция (сумма по модулю два);

 - конъюнкция;

 - эквиваленция;

 - дизъюнкция.

2. Способы задания булевых функций

 - аналитический;

 - матричный;

 - в виде формулы (с помощью таблицы истинности);

 - с помощью графов.

3. Применяя словарь перевода на язык алгебры логики изобразить кругами Эйлера следующие операции:

- отрицание (инверсия);

 

- нестрогая дизъюнкция (соединительная);

 

- строгая дизъюнкция (разделительная);

 

- импликация, следование;

 

- тождественность, равносильность, эквиваленция.

 

Тест к модулю 11 [Теория кодирования]

1. Понятие кодирование означает

 - суждения,т. е. мысли, связывающие понятия между собой;

 - преобразование информации в форму, удобную для передачи по определённому каналу связи;

 - восстановление принятого сообщения из закодированного вида в общепринятый, доступный для потребителя.

1. Современная криптография включает в себя разделы:

 - мысленные логические приёмы;

 - анализ, синтез, сравнение, абстрагирование, обобщение;

 - симметричные криптоносители; системы электронной подписи, управление ключами, криптосистемы с открытым ключом.

1. К свойствам информации можно отнести:

 - представление знаний, моделирование рассуждений, диалоговое общение человека и машины;

 - запоминаемость (возможность сохранения), передача без искажений, воспроизведение, преобразование в разной форме (копирование);

 - имитационное моделирование, теория развития решений, искусственный интеллект.

1. Проблемы кодирования:

 - создание шифра кодирования,

 - создание специальных корректирующих кодов для поиска и исправления ошибок, возникающих в результате передачи и хранения информации;

 - минимизацияизбыточной информации для успешной коррекции и сокращения потерь в скорости передачи сообщений.

 

 

Модуль 11 [Теория автоматов]

1. Определение конечных автоматов:

 - теоретическая информация математического содержания с элементами классической логики воплощает на практике идею перехода от математики фундаментальной к математике функциональной;

 - связь релейно – контактных схем с формулами алгебры логики и их использование для описания функционирования автоматов способствовали развитию и применению математической логики и теории автоматов;

 - абстрактная модель устройства, функционирующего в дискретном времени, которая перерабатывает последовательность входных сигналов (стимулов) и превращает их в последовательность выходных сигналов (реакций).

1. Виды автоматов:

 - теория сигналов и кодирования;

 - функционирование систем естественного и искусственного происхождения;

 - информационные, управляющие, вычислительные.

1. Способы задания конечных автоматов:

 - логическая, комбинационная, функциональная;

 - аналитический (с помощью формул), табличный (матрицы переходов и выходов). графический (с помощью графов);

 - конструктивный, тождественный, равносильный, тождественно-истинный или тавтологичный.

1. Задачи теории автоматов:

 - синтеза, анализа, композиции (декомпозиции);

 - шифрования, кодирования,контроля;

 - выбор модуля, цифровой метод, коррекция.