дай БОГ

Question 1

Высказывание

Answer 1

повествовательное предложение, для которого имеет смысл говорить о его истинности или ложности.

Question 2

Логическая переменная

Answer 2

это переменная, обозначающая любое высказывание, которая может принимать логические значения «истина» или «ложь».

Question 3

Функция истинности

Answer 3

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

Question 4

Элементарное высказывание

Answer 4

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

Question 5

Сложное высказывание

Answer 5

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

Question 6

Число строк (наборов логических переменных) в таблице истинности

Answer 6

зависит от числа N логических переменных и равно 2^N

Question 7

Алфавит формул алгебры высказыванием содержит:

Answer 7

1) логические константы: 1, 0;
2) логические переменные: А, В, С…;
3) логические операции: ¬ , ∧ , ∨ , ⇒, ⇔;
4) скобки, меняющие приоритет логических операций.

Question 8

Тождественно истинные формулы (тавтологии)

Answer 8

формулы, принимающие значение «истина» на всех наборах логических переменных.

Question 9

Тождественно ложные формулы (противоречия)

Answer 9

формулы, принимающие значение «ложь» на всех наборах логических переменных.

Question 10

Выполнимые формулы

Answer 10

формулы, принимающие значение «истина» хотя бы на одном наборе логических переменных.

Question 11

Равносильные формулы

Answer 11

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

Question 12

Основные равносильности логики высказываний.

Answer 12

Ассоциативность
Коммутативность
Дистрибутивность
Закон Де Моргана
(их вообще 12)

Question 13

Три способа проверки правильности логического рассуждения.

Answer 13

1. По определению, проверить таблицей истинности конъюнкции всех посылок.
2. Формула D логически следует из формулы P, тогда и только тогда, когда P→D тавтология.
3. Сокращенный. Рассуждение является неправильным, если найдется набор значений переменных такой, что P = И, а заключение D = Л.

Question 13

Логическое следование

Answer 13

Формула А логически следует из формулы В если не существует такой интерпритации что В истина а А ложна

Question 14

Булевы функции

Answer 14

функция, которая принимает 2 значения 0 и 1 и зависящая от переменных, каждая из которых так же может принимать 2 значения 0 и 1, называется булевой или переключательной

Question 14

ДНФ

Answer 14

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

Question 15

КНФ

Answer 15

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

Question 16

Минтерм

Answer 16

функции, которые принимают единичное значение только на одном наборе

Question 17

Совершенная ДНФ

Answer 17

функция представлена в виде дизъюнкции минтермов n аргументов.

Question 18

теорема разложения для ДНФ

Answer 18

Эта теорема говорит, что любое логическое высказывание можно представить в виде дизъюнкции (логического ИЛИ) конъюнкций (логического И) переменных или их отрицаний.

Question 19

Минимальная ДНФ

Answer 19

ДНФ, которое содержит минимальное количество конъюнкций и дизъюнкций, называется минимальной.

Question 19

Сокращенная ДНФ

Answer 19

Это ДНФ, полученная после всех склеиваний и поглощений из СДНФ.

Question 19

Сокращенная КНФ

Answer 19

это представление булевой функции в виде КНФ, в котором количество конъюнкций и литералов минимально, но может быть больше, чем в минимальной КНФ.

Question 20

Минимальное КНФ

Answer 20

это наиболее компактное представление булевой функции в виде конъюнкции дизъюнкций.

Question 20

Метод Квайна (склеивание)

Answer 20

Суть метода Квайна весьма проста. Основу его составляет теорема склеивания, которая применяется к каждой паре минтермов заданной функции.

Question 20

Импликанта

Answer 20

Всякую функцию ф будем называть импликантой функции f, если все минтермы функции ф входят в множество минтермов функции ƒ

Question 20

Метод Петрика

Answer 20

метод для получения всех минимальных ДНФ из таблицы простых импликант.

Question 21

Совершенная КНФ

Answer 21

функция представлена в виде коньюнкции макстермов n аргументов.

Question 21

Макстерм

Answer 21

это булева функция, которая, в отличие от минтерма, принимает единичное значение на всех наборах, за исключением одного. На этом единственном наборе макстерм принимает нулевое значение.

Question 21

Теорема разложения для КНФ

Answer 21

Эта теорема говорит, что любое логическое высказывание можно представить в виде конъюнкции дизъюнкций переменных или их отрицаний.

Question 22

Понятие функциональной полноты

Answer 22

Система булевых функций называется полной, если для любой булевой функции можно построить равную её функцию, представляющую собой результат суперпозиции функций

Question 23

самодвойственная функция

Answer 23

это такая булева функция, которая остается той же самой, если поменять все ее входные переменные на противоположные. Другими словами, если мы заменим все 0 на 1, и наоборот, то функция не изменится.

Question 24

Линейные функции

Answer 24

Функция называется линейной, если в алгебре Жегалкина она может быть представлена в виде полинома первой степени (т. е. без конъюнкций).

Question 25

монотонная функция

Answer 25

Булева функция n аргументов является монотонной, если при любом возрастании наборов значения функции не убывают

Question 26

Функции, сохраняющие единицу

Answer 26

Булева функция сохраняет единицу, если на единичном наборе значений аргументов она принимает единичное значение

Question 27

Функции, сохраняющие нуль

Answer 27

Булева функция сохраняет нуль, если на нулевом наборе она принимает нулевое значение. Нулевой набор состоит из n нулей, где n – число аргументов булевой функции.

Question 28

Теорема Поста о функциональной полноте

Answer 28

Система булевых функций называется функционально полной, если она содержит хотя бы одну нелинейную функцию, хотя бы одну немонотонную, хотя бы одну не самодвойственную, хотя бы одну, не сохраняющую единицу, и хотя бы одну, не сохраняющую нуль

Question 29

Одноместный предикат

Answer 29

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

Question 30

Предметная область предиката

Answer 30

Предметная область (область определения) предиката – это множество M, на котором определен предикат.

Question 31

Предметные переменные

Answer 31

Предметные переменные – это элементы множества M, на котором определен предикат

Question 32

Область истинности предиката

Answer 32

Областью истинности предиката P(x), заданного на множестве M, называется совокупность всех x из M, при которых данный предикат обращается в истинное высказывание

Question 33

n-местный предикат

Answer 33

n-местным предикатом называется произвольная функция переменных P(x1,…,xn), определенная на множестве M  M1…Mn и принимающая (логические) значения из множества {0,1}.
Например, P(x,y) = «y делится на x без остатка» – предикат от двух переменных

Question 34

48. Тождественно истинный предикат. 49. Тождественно ложный предикат. 50. Выполнимый предикат.

Answer 34

Читать в файле

Question 35

Логические операции над предикатами

Answer 35

Коньюнкция, дизъюнкция, отрицание предиката, импликация и эквиваленция

Question 36

Кванторы

Answer 36

это общее название для логических операций, ограничивающих область истинности какого-либо предиката

Question 37

Связывание квантором всеобщности

Answer 37

Операцией связывания квантором всеобщности называется правило, по которому каждому одноместному предикату Р(x), определенному на множестве М, сопоставляется высказывание, обозначаемое УхP(х), которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае.

Question 38

Связывание квантором существовании

Answer 38

Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, ставится в соответствие высказывание, обозначаемое ЭхР(х), которое ложно в том и только в том случае, когда Р(х) тождественно ложен, и истинно в противном случае.

Question 39

Квантор для многоместных предикатов

Answer 39

Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х, у) одноместный предикат xP(х,у) или ЭхР(х, у), зависящий от у и не зависящий от х. К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь различных высказываний:

Question 40

Автоматные описание

Answer 40

таблица которая описывает комбинационную схему из входов и выходов данных программы.

Question 41

Синтез комбинационных схем

Answer 41

ТАБЛИЦА
ПРИОРИТЕТ (ОТРИЦАНИЕ, КОНЪЮНКИЦЯ, ДИЗЪЮНКИЦИЯ, ИМПЛИКАЦИЯ, ЭКВИВАЛЕНЦИЯ, СЛОЖЕНИЕ ПО MOD 2(

Question 42

Приведенная форма

Answer 42

Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции {¬,∧,∨}, причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Question 43

Предваренной нормальной формой

Answer 43

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

Question 44

Алгоритм получения ПНФ

Answer 44

1. перейти от импликации и эквиваленции к {∨,∧,¬} и тд сморти файл короче заебал пункт 67