Опрос_мат. логика. Логика наука о способах доказательств или опровержений. Высказывание
 Скачать 13 Kb.
|
|
ЛОГИКА – наука о способах доказательств или опровержений. ВЫСКАЗЫВАНИЕ – утвердительное предложение о котором можно сказать истинно оно или ложно. ПРОСТОЕ ВЫСКАЗЫВАНИЕ – такое высказывание которое является неделимым по смыслу. СЛОЖНЫЕ ВЫСКАЗЫВАНИЯ – высказывания которые состоят из простых и соединены логическими связками. ОТРИЦАНИЕ (инверсия) – логическая операция при которой высказывание ложно если НЕ А - ложно. КОНЪЮНКЦИЯ (лог умножение) – сложное логическое высказывание которое истинно при истинности всех составляющих этого высказывания, иначе ложно. ДИЗЪЮНКЦИЯ (лог сложение) – сложное логическое высказывание которое ложно только при ложности всех составляющих этого высказывания иначе истина. ИМПЛИКАЦИЯ (лог следование) – сложное логическое высказывание которое ложно, когда 1 высказ – истина, 2 высказ – ложь. ЭКВИВАЛЕНЦИЯ (лог тождество) – сложное логическое высказывание которое истинно при истинности всех исходных высказываний. СЛОЖЕНИЕ ПО МОДУЛЮ ДВА – сложное логическое высказывание которое истинно, если значение исходных высказываний не совпадает, иначе ложно. ТАВТОЛОГИЯ - если формула превращается в истинное высказывание при подстановке вместо переменных любых высказ. ПРОТИВОРЕЧИЕ – если формула превращается в ложное высказывание при подстановке вместо переменных любых высказ. ВЫПОЛНИМАЯ - если сущ конкретные высказ, которые превращ исходную формулу в истинное высказывание. ОПРОВЕРЖИМАЯ - если сущ конкретные высказ, которые превращ исходную формулу в ложное высказывание. Булевой функцией (или функцией алгебры логики) называется функция, заданная на множестве {0;1} и принимающая значение на том же множестве. БУЛЕВАЯ ПЕРЕМЕННАЯ – переменная принимающая значение 0, 1. СДНФ – функция которая представлена в виде дизъюнкций простых конъюнкций . СКНФ – такая КНФ, в которой в каждую дизъюнкцию входят все переменные. ПОЛИНОМ ЖЕГАЛКИНА - это полином, коэф которого это либо числа 0, либо 1, в кач-ве операций выступает конъюнкция и сложение по модулю 2. КЛАССЫ БФ: Т0 - класс БФ, сохр константу 0, значение функции на 0 наборе равно 0. Т1 - класс БФ, сохр константу 1. S (самодвойственная) – функция двойственна сама себе. M (монотонная) – если для двух наборов выполняется условие. L (линейная) – если полином жегалкина имеет вид a0+a1x1+a2x2+anxn Две функции называют ЭКВИВАЛЕНТНЫМИ, если одним и тем же набором значений переменных соответствует одним значениям функций. ПРОСТАЯ КОНЪЮНКЦИЯ – это либо сами переменные либо их отриц. Простая дизъюнкция - одна или несколько переменных, при чем каждая переменная входит в дизъюнкцию не более одного раза. Классы Поста: Множества Т0, Т1, S, M, L - называются классами Поста Полнота системы (критерий Поста): С точки зрения таблицы принадлежности к классам Поста множества функций являются полным, если в каждом столбце стоит хотя бы один минус. Штрих Шеффера: Отрицание конъюнкции. Стрелка Пирса: Отрицание дизъюнкции. Операция запрета – сложная логическая операция, истинная тогда, когда первое ложно, а второе истинно, в остальных случаях она ложна. Монотонность: Булева функция называется монотонной, если из того, что она принимает значение 1 на некотором наборе аргументов , следует, что она принимает значение 1 на всяком наборе аргументов , который получается из данного путём замены произвольного числа нулей на единицы. |