И код направления подготовки
жүктеу/скачать 341.63 Kb.
|
- Бұл бет үшін навигация:
- Определение.
- Нормальные формы формул
| Булева алгебра. Пусть множество Х состоит из двух элементов 0 и 1, Х={0,1}, Xn = {(x1, …, xn) | i = , xi X}
Определение. Всякую переменную, которая может принимать одно из двух возможных значений, обозначаемых 0 (ложь) и 1 (истина), назовем булевой (логической) переменной. Определение. Функция f(x1, …, xn), принимающая вместе со своими переменными значения на множестве {0,1}, называется булевой функцией (функцией алгебры логики – ФАЛ). Т.е., это функция, у которой все аргументы есть логические переменные, и сама функция принимает только логические значения. Определение . Совокупность координат некоторого фиксированного вектора (х1, …, хn) Х называется двоичным набором. Совокупность значений переменных булевой функции будем называть набором. Например, для булевой функции f(x1, x2, x3) совокупность значений x1=1, x2=0, x3=1 записывается как набор 101. Булева функция может быть задана с помощью таблицы – перечислением ее значений на всех наборах. Множество наборов принято записывать в лексикографическом порядке, так что каждый набор представляет собой код двоичного числа. Соответствующее ему десятичное число будем называть номером набора. Пусть (х1, х2, …, хn) – логический набор, тогда х12n-1+х22n-2+…+xn20 – номер набора. Например: (0,1,1) = 022 + 121+120 = 3 (0,0,1,1) = 023+022 +121+120 = 3 Вопросы для закрепления: Что представляет булева алгебра? Приведите пример. Что такое булева функция? Как может быть задана булева функция? Приведите пример логических функций одной и двух переменных. Что называют двоичным набором? Что такое номер набора? Литература: Основная [1]; дополнительная [3]; Интернет ресурсы [1]-[4] Тема 5 Нормальные формы формул Количество часов 1 Основные вопросы/план темы: Нормальные формы формул. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы. Приведение к ДНФ (СДНФ) и КНФ (СКНФ). Разрешимость. Тезисы лекции*: жүктеу/скачать 341.63 Kb. Достарыңызбен бөлісу:
|