Комплекти и отношения.

Комплекти и техните спецификации. Операции на снимачната-ти. Диаграми на Ойлер-Вен. Кардиналност. Най ограничени и изброимо множество. Връзки. Свойства на отношения. Операции на отношения. Една връзка равностойност. Крайни удара, както и на връзка равностойност. Връзката на частичен ред и строга. Функции и дисплей. Инжектиране, surjection, наслагване, Биекция, обратна функция.

Референции: [1], стр. 5-10; [3], част 2; [4], Ch. 1-3; [5], Ch. 1.

Булева алгебра. Елементи на математическата логика.

Булеви функции. Методи за задача. Значително и манекени. Булева формула. Основни свойства на логическите операции. Идеално нормална форма. Poly-н Zhegalkin. Затворени класове функции. Функционално цялостни системи. Теорема на функционална пълнота. Примери за функционално пълна основи. Проблемът за минимизиране на булеви функции. Схеми на функционални елементи. Крайни автомати. Официално теория. Идеята на Пропозиционални-ТА. Тавтология. Пропозиционални смятане. предикатна логика.

Референции: [1], стр. 14-53; [2], гл. 3.8; [3], 1,4 части; [4], Ch. 4, 5; [5], Ch. 3.4.

Еквивалентност булеви формули.

Булева функция може да се настрои или чрез използване на истината маси (еднозначно) или чрез логически формули (не еднозначно). Ако масата за истина от две булеви формули са едни и същи, тези формули са еквивалентни и определят една и съща Булева функция.

Пример. Проверете за еквивалентност булеви формули:

Ние се изгради една маса истина за функцията.

Резултати колони в таблиците за истинност съвпадат оттам Формула еквивалент.

Значително и манекени.

Променлива () Булева функция се нарича сляпо. ако има равенство

за всички променливи. Делото срещу г-н променлива, наречена от съществено значение. Настройва стойностите на променливите в горното уравнение се наричат ​​съседни на променливата.

Пример. Определяне на основните функции и фиктивни променливи (11,110,011).

За удобство, ние даваме една маса на истината.

Ние проверяваме дали дадена променлива е значителна или фиктивна. Помислете за стойността на функцията на снимачната площадка на прилежащата към променливата:

. Следователно, на променливата - Има Най.

Сега помислете стойностите на функцията в комплекти, техният съсед на променливата:

. Следователно, променливата - су nificant.

Помислете за стойността на функцията на снимачната площадка на прилежащата към променливата:

За всички двойки съседни стойности в променливи комплекти депозитите на променлива функция на приема равни стойности, проследи-ТА, променлива - манекен.

Представителства на булеви функции на разширения в променливите.

Perfect разделителен нормална форма (PDNF) за булева функция. не е равна на идентичност-venno нула, има следния вид:

където символът се определя, както следва:

Алгоритъм за изграждане PDNF.

1. изграждане на истината маса на Булева функция.

2. Всяка единица стойност на булева функция ще съответства на елементарни съюза. когато - в съответствие с набор от ценности-правителствени промени. В съюзи пишем. ако. и. ако. Съюзи свързват знак.

Perfect функция съединителната нормална форма (SKNF). различни от еднакви елементи е както следва:

Алгоритъм за изграждане SKNF.

1. изграждане на истината маса на Булева функция.

2. Всяка нулева стойност на булева функция ще съответства на една елементарна дизюнкция. където - подходящ набор от променливи. Дизюнкция пишем. ако. и. ако. Разделение свързан знак.

Всеки Булева функция може да се представи като полином Zhegalkin:

къде. където знак означава модул 2 сума.