дай БОГ Flashcards
1231231231
Высказывание
повествовательное предложение, для которого имеет смысл говорить о его истинности или ложности.
Логическая переменная
это переменная, обозначающая любое высказывание, которая может принимать логические значения «истина» или «ложь».
Функция истинности
это зависимость, которая устанавливает, будет ли высказывание истинным или ложным в зависимости от значений его логических переменных.
Элементарное высказывание
высказывание, представляющее собой одно утверждение.
Сложное высказывание
высказывание, образованное из элементарных высказываний с помощью грамматических связок.
Число строк (наборов логических переменных) в таблице истинности
зависит от числа N логических переменных и равно 2^N
Алфавит формул алгебры высказыванием содержит:
1) логические константы: 1, 0;
2) логические переменные: А, В, С…;
3) логические операции: ¬ , ∧ , ∨ , ⇒, ⇔;
4) скобки, меняющие приоритет логических операций.
Тождественно истинные формулы (тавтологии)
формулы, принимающие значение «истина» на всех наборах логических переменных.
Тождественно ложные формулы (противоречия)
формулы, принимающие значение «ложь» на всех наборах логических переменных.
Выполнимые формулы
формулы, принимающие значение «истина» хотя бы на одном наборе логических переменных.
Равносильные формулы
формулы, принимающие одинаковые истинностные значения при любых наборах своих логических переменных.
Основные равносильности логики высказываний.
Ассоциативность
Коммутативность
Дистрибутивность
Закон Де Моргана
(их вообще 12)
Три способа проверки правильности логического рассуждения.
- По определению, проверить таблицей истинности конъюнкции всех посылок.
- Формула D логически следует из формулы P, тогда и только тогда, когда P→D тавтология.
- Сокращенный. Рассуждение является неправильным, если найдется набор значений переменных такой, что P = И, а заключение D = Л.
Логическое следование
Формула А логически следует из формулы В если не существует такой интерпритации что В истина а А ложна
Булевы функции
функция, которая принимает 2 значения 0 и 1 и зависящая от переменных, каждая из которых так же может принимать 2 значения 0 и 1, называется булевой или переключательной
ДНФ
Если булева формула записана в виде дизъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо конъюнкцию некоторых аргументов, то эта формула является представленной в дизъюнктивной нормальной форме (ДНФ).
КНФ
Если булева формула записана в виде конъюнкции выражений, каждое из которых представляет собой либо отдельный аргумент (с инверсией или без инверсии), либо дизъюнкцию некоторых аргументов, то эта формула является представленной в конъюнктивной нормальной форме (КНФ).
Минтерм
функции, которые принимают единичное значение только на одном наборе
Совершенная ДНФ
функция представлена в виде дизъюнкции минтермов n аргументов.
теорема разложения для ДНФ
Эта теорема говорит, что любое логическое высказывание можно представить в виде дизъюнкции (логического ИЛИ) конъюнкций (логического И) переменных или их отрицаний.
Минимальная ДНФ
ДНФ, которое содержит минимальное количество конъюнкций и дизъюнкций, называется минимальной.
Сокращенная ДНФ
Это ДНФ, полученная после всех склеиваний и поглощений из СДНФ.
Сокращенная КНФ
это представление булевой функции в виде КНФ, в котором количество конъюнкций и литералов минимально, но может быть больше, чем в минимальной КНФ.
Минимальное КНФ
это наиболее компактное представление булевой функции в виде конъюнкции дизъюнкций.
Метод Квайна (склеивание)
Суть метода Квайна весьма проста. Основу его составляет теорема склеивания, которая применяется к каждой паре минтермов заданной функции.
Импликанта
Всякую функцию ф будем называть импликантой функции f, если все минтермы функции ф входят в множество минтермов функции ƒ
Метод Петрика
метод для получения всех минимальных ДНФ из таблицы простых импликант.
Совершенная КНФ
функция представлена в виде коньюнкции макстермов n аргументов.
Макстерм
это булева функция, которая, в отличие от минтерма, принимает единичное значение на всех наборах, за исключением одного. На этом единственном наборе макстерм принимает нулевое значение.
Теорема разложения для КНФ
Эта теорема говорит, что любое логическое высказывание можно представить в виде конъюнкции дизъюнкций переменных или их отрицаний.
Понятие функциональной полноты
Система булевых функций называется полной, если для любой булевой функции можно построить равную её функцию, представляющую собой результат суперпозиции функций
самодвойственная функция
это такая булева функция, которая остается той же самой, если поменять все ее входные переменные на противоположные. Другими словами, если мы заменим все 0 на 1, и наоборот, то функция не изменится.
Линейные функции
Функция называется линейной, если в алгебре Жегалкина она может быть представлена в виде полинома первой степени (т. е. без конъюнкций).
монотонная функция
Булева функция n аргументов является монотонной, если при любом возрастании наборов значения функции не убывают
Функции, сохраняющие единицу
Булева функция сохраняет единицу, если на единичном наборе значений аргументов она принимает единичное значение
Функции, сохраняющие нуль
Булева функция сохраняет нуль, если на нулевом наборе она принимает нулевое значение. Нулевой набор состоит из n нулей, где n – число аргументов булевой функции.
Теорема Поста о функциональной полноте
Система булевых функций называется функционально полной, если она содержит хотя бы одну нелинейную функцию, хотя бы одну немонотонную, хотя бы одну не самодвойственную, хотя бы одну, не сохраняющую единицу, и хотя бы одну, не сохраняющую нуль
Одноместный предикат
Одноместным предикатом P(x) называется произвольная функция одной переменной x, значениями которой являются высказывания об объектах, представляющих значения аргумента.
Предметная область предиката
Предметная область (область определения) предиката – это множество M, на котором определен предикат.
Предметные переменные
Предметные переменные – это элементы множества M, на котором определен предикат
Область истинности предиката
Областью истинности предиката P(x), заданного на множестве M, называется совокупность всех x из M, при которых данный предикат обращается в истинное высказывание
n-местный предикат
n-местным предикатом называется произвольная функция переменных P(x1,…,xn), определенная на множестве M M1…Mn и принимающая (логические) значения из множества {0,1}.
Например, P(x,y) = «y делится на x без остатка» – предикат от двух переменных
- Тождественно истинный предикат. 49. Тождественно ложный предикат. 50. Выполнимый предикат.
Читать в файле
Логические операции над предикатами
Коньюнкция, дизъюнкция, отрицание предиката, импликация и эквиваленция
Кванторы
это общее название для логических операций, ограничивающих область истинности какого-либо предиката
Связывание квантором всеобщности
Операцией связывания квантором всеобщности называется правило, по которому каждому одноместному предикату Р(x), определенному на множестве М, сопоставляется высказывание, обозначаемое УхP(х), которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае.
Связывание квантором существовании
Операцией связывания квантором существования называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, ставится в соответствие высказывание, обозначаемое ЭхР(х), которое ложно в том и только в том случае, когда Р(х) тождественно ложен, и истинно в противном случае.
Квантор для многоместных предикатов
Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к предикату Р(х,у) по переменной х ставит в соответствие двухместному предикату Р(х, у) одноместный предикат xP(х,у) или ЭхР(х, у), зависящий от у и не зависящий от х. К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь различных высказываний:
Автоматные описание
таблица которая описывает комбинационную схему из входов и выходов данных программы.
Синтез комбинационных схем
ТАБЛИЦА
ПРИОРИТЕТ (ОТРИЦАНИЕ, КОНЪЮНКИЦЯ, ДИЗЪЮНКИЦИЯ, ИМПЛИКАЦИЯ, ЭКВИВАЛЕНЦИЯ, СЛОЖЕНИЕ ПО MOD 2(
Приведенная форма
Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции {¬,∧,∨}, причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.
Предваренной нормальной формой
Предваренной нормальной формой для формулы логики пре- дикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы.
Алгоритм получения ПНФ
- перейти от импликации и эквиваленции к {∨,∧,¬} и тд сморти файл короче заебал пункт 67
