Конъюнктивная и дизъюнктивная нормальные формы

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

Определение Конъюнктивная нормальная форма (КНФ) от переменных x1,x2,...,xn — это формула вида D1∧D2∧…∧Dm, где Di,i=1,m¯¯¯¯¯¯ — элементарная дизъюнкция, которая содержит некоторые из литералов переменных x1,x2,…,xn.

Если же в каждую элементарную дизъюнкцию Di для каждогономера j=1,n¯¯¯¯¯ входит в точности один из литералов x˜j, то КНФ называется совершенной конъюнктивной нормальной формой (СКНФ).

Логика предикатов. Кванторы

Определенным на множествах n-местным предикатом называется предложение, содержащее переменных , превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств соответственно.

Ква́нтор — общее название для логических операций, ограничивающих область истинности какого-либопредиката и создающих высказывание. Чаще всего упоминают:

· Квантор всеобщности (обозначение: , читается: «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).

· Квантор существования (обозначение: , читается: «существует…» или «найдётся…»).

В математической логике приписывание квантора к формуле называется связыванием или квантификацией.

Булевы алгебры

Булевой алгеброй называется непустое множество A с двумя бинарными операциями (аналогконъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

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

Вероятностная логика

Вероятностная логика — логика, в которой высказываниям приписываются не исключительно значенияистины и лжи как в двузначной логике, но непрерывная шкала значений истинности от 0 до 1, так что, ноль соответствует невозможному событию, единица — практически достоверному. Значения истинности в вероятностной логике называются вероятностями истинности высказываний, степенями правдоподобия или подтверждения.

Математическая индукция

метод математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.

Теория алгоритмов