Функционально полная система булевых функций
Система функций из
(где
− множество всех возможных булевых функций, зависящих от любого числа переменных), в которой любая булева функция может быть записана в виде формулы через функции этой системы (в виде суперпозиции функций из этой системы).
Функционально полная система булевых функций в слабом смысле
Система функций из
, суперпозицией которых может быть представлена любая функция из некоторого множества булевых функций и в которой допускаются константы 0 и 1.
То же, что и ослаблено функционально полная система.
Функция, сохраняющая единицу (1)
Булева функция , которая на единичном наборе равна 1, т.е.
.
Функция, сохраняющая ноль (0)
Булева функция , которая на нулевой наборе равна 0, т.е.
.
Эквивалентные формулы
Формулы, представляющие одну и ту же функцию (то же, что и равносильные формулы).
Элементарная дизъюнкция
Дизъюнкция любого числа булевых переменных, взятых с отрицанием или без него, в которой каждая переменная встречается не более одного раза.
Элементарная конъюнкция
Конъюнкция любого числа булевых переменных, взятых с отрицанием или без него, в которой каждая переменная встречается не более одного раза.
Логика высказываний и логика предикатов
-местный предикат
Предикат, содержащий переменных (
аргументов) (обозначается
).
Аксиомы логики высказываний
Аксиомами логики высказываний является некоторое множество общезначимых формул логики высказываний.
Антецедент
В импликации высказывание
называется антецедентом.
То же, что и условие, посылка.
Атом (в логике высказываний)
Высказывание, которое соответствует простому повествовательному предложению, т.е. не имеет составных частей.
То же, что и элементарное высказывание, атомарная формула.
Атом (в логике предикатов)
Если -
-местный предикат и
- термы, то
называется атомом.
То же, что и элементарная формула логики предикатов.
Атомарная формула
То же, что и элементарное высказывание, атом.
Вывод в исчислении высказывания
Всякая последовательность формул такая, что для любого
формула
есть либо аксиома, исчисления высказываний, либо непосредственное следствие каких-либо предыдущих формул, полученных по правилу вывода.
Выполнимые формулы
Все формулы, не относящиеся к противоречивым, образуют множество выполнимыхформул.
Высказывание
Утверждение или повествовательное предложение, о котором можно сказать, истинно оно или ложно, но ни то и другое одновременно.