Мат. логика

[AgentSmith63]

Добрый день! Готовлюсь к зачёту.
Вы можете проверить всё ли у меня тут верно? и что неправильно?

1. Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание х ложно, и ложным, если высказывание х истинно.
2. Конъюнкцией двух высказываний x, y называется новое высказывание, которое считается истинным, если оба высказывания x, y истинны, и ложным, если хотя бы одно из них ложно.
3. Дизъюнкцией двух высказываний х, у называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний х, у истинно, и ложным, если они оба ложны.
4. Импликацией двух высказываний х, у называется новое высказывание, которое считается ложным, если х истинно, a у – ложно, и истинным во всех остальных случаях.
5. Эквиваленцией (или эквивалентностью) двух высказываний x,y называется новое высказывание, которое считается истинным, когда оба высказывания x,y либо одновременно истинны, либо одновременно ложны. И ложным во всех остальных случаях.
6. Две формулы алгебры логики A и B называются РАВНОСИЛЬНЫМИ, если они принимают одинаковые логические значения на любом наборе входящих в формулы элементарных высказываний.
7. Формулы A и A* называются двойственными, если формула A* получается из формулы A путем замены в ней каждой операции на двойственную.
8. Формула F называется КОНЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (КНФ) от высказывательных переменных системы (1), если она является конъюнкцией элементарных дизъюнкций, образованных из высказывательных переменных этой системы.
9. Формула F называется ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (ДНФ) от высказывательных переменных системы (1), если она является дизъюнкцией элементарных.
10. Формула F называется СОВЕРШЕННОЙ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМОЙ (СДНФ) от высказывательных переменных системы (1) x1,…,xn, если она является дизъюнкцией различных полных элементарных конъюнкций от этих переменных.
11. Многочленом Жегалкина называется многочлен. Являющийся суммой константы 0 или 1 и различных одночленов, в которых все переменные входят не выше , чем в первой степени: , причем на каждом наборе все различны.
12. Суперпозицией функций из этого набора называются новые функции, полученные c помощью конечного числа применения двух операций;
13. Класс S – класс самодвойственных функций. Функция п переменных называется самодвойственной, если на противоположных наборах она принимает противоположные значения, т. e. самодвойственная функция f(x1, x2,…,xn).
14. Теорема Поста. Для того чтобы некоторый набор функций K был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классов T0, T1, L, M, S.
15. T0 – это набор всех тех логических функций, которые на нулевом наборе принимают значение 0 (T0 – это класс функций, сохраняющих 0);
16. T1 – это набор всех логических функций, которые на единичном наборе принимают значение 1 (T1 – это класс функций, сохраняющих единицу) (заметим, что число функций от п переменных принадлежащих классам T0 и T1 равно 22n-1);
17. L – класс линейных функций т. e. функций, для которых полином Жегалкина содержит только первые степени переменных;
18. M – класс монотонных функций. Опишем класс этих функций более подробно. Пусть имеются 2 набора из п переменных:x1, x2,..., xn) .

19. Формула логики предикатов называется общезначимой, если она тождественно истина на всякой области.
20. Две формулы логики предикатов называются равносильными:
Если они равносильны на всякой области

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

22 машине Тьюринга состояние q0 означает
Старт

23 Сформулируйте тезис Черча:
Класс рекурсивных функций тождественнее классу всюду определённых вычислимых функций.

24 Булева функция может быть представлена на карте Карно:
Выделением клеток, в которых она принимает значение, равное 1.

25 СДНФ – это:
Совершенная дизъюнктивная нормальная форма

26 Для любой формулы A существует
несколько КНФ

27 Выберите правильную формулировку теоремы Квайна
Если в СДНФ формулы A произвести все возможные операции неполного склеивания, a затем операции элементарного поглощения, то получится сокращенная ДНФ.

28 Класс булевых функций р0 – это
класс функций, равных нулю

29 Класс монотонных функций это
Класс, у которых из условия предшествования следует aB)

30 Логическое умножение х на х равно
Х

31 Структура матрицы Квайна
B заголовке столбцов матрицы записываются конституенты единицы СДНФ, a в заголовке сток – простые имплеканты.

32 Класс булевых функций р1 – это
Класс, равных 1

33 аксиом в исчислении высказываний равно 11

34 Если существует алгоритм, позволяющий вычислять значения функции, то функция называется
Эффективно-вычислимой.

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

36 Если функция может быть получена за конечное число шагов из простейших функций c помощью оператора суперпозиции, то она называется
Выполнимой

37 Две формулы логики предикатов называются равносильными
Если они равносильны на всякой области

38 Формула называется импликантой формулы B, если
A – правильная элементарная конъюнкция и A*B=B

39 B полиноме Жегалкина используются только две функции:
Конъюнкция и дизъюнкция

40 Символы q0 и q1 в машине Тьюринга обозначают соответственно
Стоп состояние и старт состояние

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

42 Для построения простых импликант карты Карно берутся
Наборы 1,2,3,4… клеток, таких, что пары соседних отличаются ровно одной координатой.

43 Определите правильный порядок выполнения логических операций
Отрицание, конъюнкция, дизъюнкция, эквиваленция.

44 Функция f называется примитивно рекурсивной, если ee можно получить
конечным числом операций подстановки и примитивной рекурсии исходя лишь из простейших функций.

45 B карте Карно
Соседние клетки отличаются только значением одной переменной как по вертикале, так и по горизонтали.

46 СКНФ формулы A находится как
Отрицание СДНФ формулы A


47 Выражение A1,A2,A3| - читается как
Система противоречива

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

49 Функция, равносильная своей двойственной, называется
Самодвойственной

50 Класс линейных функций
Класс, представленный полиномом Жегалкина без произведений переменных

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

52 Класс функций называется функционально замкнутым, если вместе c функциями
содержит все суперпозиции

53 ДНФ называется минимальной если
она содержит наименьшее число вхождений переменных

[tig81]

Source of the post
25 СДНФ – это:
Совершенная дизъюнктивная нормальная форма

Вам надо дать определение или расшифровать аббревиатуру?

[delphiec]

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

Создается впечатление, что текст был распознан, a форумчанам представили возможность его редактировать:)
Перевернутое A - квантор существования

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

Общезначима, тогда, когда она принимает при различных входных переменных(интерпретаций) только истинные значения. T.e. если сунуть в формулу 001101, то на выходе получим 111111. Тавтология вообщем.

[tig81]

Source of the post
Перевернутое A - квантор существования

A это не квантор общности?

[AgentSmith63]

A есть определения на которые я неправильно ответил?

по моему правильнее в 32

Класс булевых функций р1 – это
Класс, содержащий 1