какая операция равносильна выражению a b

Какая операция равносильна выражению a b

2) Логическое сложение или дизъюнкция:

Таблица истинности для дизъюнкции

3) Логическое отрицание или инверсия:

Таблица истинности для инверсии

4) Логическое следование или импликация:

«A → B» истинно, если из А может следовать B.

Обозначение: F = A → B.

Таблица истинности для импликации

5) Логическая равнозначность или эквивалентность:

Источник

Равносильные формулы алгебры высказываний

Равносильные формулы алгебры высказываний

Равносильные формулы алгебры высказываний

Например, равносильны формулы:

Тождественно истинная формула

Тождественно ложная формула

Выполнимая формула

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

Группы равносильностей

Важнейшие равносильности алгебры высказываний можно разбить на следующие группы.

Равносильности алгебры Буля

Равносильности, выражающие одни логические операции через другие

$X\leftrightarrow Y\equiv (X\rightarrow Y)\wedge (Y\rightarrow X)$

$X\leftrightarrow Y\equiv (\overline < X >\vee Y)\wedge (\overline < Y >\vee X)$

$X\leftrightarrow Y\equiv (X\wedge Y)\wedge (\overline < Y >\wedge \overline < X >)$

$X\rightarrow Y\equiv \overline < X >\vee Y$

$X | Y\equiv \overline < X\cdot Y >$

$X \downarrow Y\equiv \overline < X\vee Y >$

$X \rightarrow Y\equiv \overline < X >\vee Y$

$X \bigoplus Y\equiv (X \cdot \bar < Y >)\vee (\bar < X >\cdot Y)$

$X \sim Y\equiv \overline < X \bigoplus Y >\equiv (XY)\vee (\bar < X >\bar < Y >)$

Далее:

Теорема об алгоритме распознавания полноты

Поверхностный интеграл первого рода и его свойства

Свойства тройного интеграла

Несобственные интегралы от неограниченной функции

Упрощение логических функций

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

Определение тройного интеграла. Теорема существования тройного интеграла

Функции 2-значной логики. Лемма о числе функций. Элементарные функции 1-ой и 2-х переменных

Нормальные формы

Теорема Остроградского

Полином Жегалкина. Пример.

Вычисление двойного интеграла. Двукратный интеграл

Вычисление криволинейного интеграла второго рода. Примеры.

Источник

Логические выражения и таблица истинности

Логические выражения и таблица истинности

Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.

Логическое выражение — составные высказывания в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

3. подсчитать количество логических операций в формуле;

4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

7. провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью.

Заполнение таблицы:

1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 2 3 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

1. В выражении две переменные А и В (n=2).

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

Источник

Какая операция равносильна выражению a b

Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

1) любая высказывательная переменная – формула;

3) только те слова являются формулами, для которых это следует из 1) и 2).

Например: или . Скобки указывают порядок выполнения действий.

Скобки в формулах можно опускать, придерживаясь следующего порядка выполнения действий: коньюнкция, дизьюнкция, импликация и эквиваленция.

Логическое значение формулы полностью определяется логическими значениями входящих в нее элементарных высказываний.

При x = 1, y = 1, z = 0 формула

Логическое значение формулы изменяется в зависимости от изменений значений элементарных высказываний, входящих в формулу. Все возможные логические значения формулы могут быть описаны полностью с помощью таблицы истинности.

Таблица истинности логических значений формулы будет следующая:

Если формула содержит n элементарных высказываний, то она принимает 2 n значений. Таблица истинности будет содержать 2 n строк.

Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения на любом наборе значений, входящих в формулы элементарных высказываний.

Следующие формулы являются равносильными:

Формула А называется тождественно истинной (или тавтологией ), если она принимает значение 1 при всех значениях входящих в нее переменных.

Следующие формулы являются тавтологиями: ,

Формула является тождественно ложной.

Отношение равносильности обладает следующими свойствами: оно рефлексивно, симметрично и транзитивно.

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула – тавтология, и обратно, если формула – тавтология, то формулы А и В равносильны.

Равносильности алгебры логики используются для того, чтобы любую формулу алгебры логики можно заменить равносильной ей формулой.

Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности

Пусть А ≡ при x = 1, значение А = 1, при х = 0, значение А = 0. Итак во всех случаях значения формулы А совпадают со значениями х, следовательно, А ≡ х.

2. Равносильности, выражающие одни логические операции через другие

Замечание. Формулы 5 и 6 получаются из 3 и 4, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.

Докажем формулы 1–4.

1) при одинаковых логических значениях x и y формулы , и – истинны, следовательно, истинной будет и коньюнкция т. е. обе части равносильности имеют одинаковые истинные значения.

2) пусть хотя бы одна из переменных x или y принимает значение ложь, тогда тоже ложь, а – истина. В то же время отрицание хотя бы одной из переменных будет истинным, следовательно, будет истиной и дизьюнкция .

Следовательно, во всех случаях обе части равносильности 3 принимают одинаковые логические значения.

Аналогично доказываются равносильности 2 и 4.

Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: коньюнкцию и отрицание или дизьюнкцию и отрицание.

3. Равносильности, выражающие основные законы алгебры логики

– комм утативность коньюнкции и дизьюнкции.

При х = 1, формулы , и будут истинны, тогда и – тоже истинна.

При х = 0, ≡ , ≡ ≡ следовательно,

Таким образом, обе части формулы 6 равносильны одной и той же формуле и поэтому принимают одинаковые логические значения. Что и требовалось доказать.

Равносильности 3-ей группы выражают основные законы алгебры логики: коммутативность, ассоциативность и дистрибутивность (относительно логических операций – коньюнкции и дизьюнкции). Эти же законы имеют место в алгебре чисел. Поэтому над формулами алгебры логики можно производить те же преобразования, которые проводятся в алгебре чисел, т. е.

1) раскрытие скобок;

2) заключение в скобках;

3) вынесения за скобки общего множителя.

Кроме этих преобразований над формулами алгебры логики можно производить и преобразования, основанные на использовании равносильностей.

Равносильные преобразования формул используют

1) для доказательства равносильностей,

2) для приведения формул к заданному виду,

3) для упрощения формул.

Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций коньюнкции и дизьюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.

1. Доказать равносильность

2. Упростить формулу

3. Доказать тождественную истинность формулы

Источник

Какая операция равносильна выражению a b

Равносильные формулы алгебры логики

Определение. Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения при любом наборе значений входящих в формулы элементарных высказываний (переменных).

Определение. Формула A называется тождественно истинной (тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных (напр., ).

Определение. Формула A называется тождественно ложной (противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных (напр., ).

Утверждение. Отношение равносильности рефлексивно, симметрично, транзитивно.

Связь между понятиями равносильности и эквивалентности: если формулы A и B равносильны, то формула A ↔ B тавтология, и обратно, если формула A ↔ B тавтология, то формулы A и B равносильны.

Равносильности алгебры логики можно разбить на 3 группы:

1. Основные равносильности.

· – законы идемпотентности;

· ;

· ;

· ;

· ;

· – закон противоречия;

· – закон исключенного третьего;

· – закон снятия двойного отрицания;

· – законы поглощения.

1. Равносильности, выражающие одни логические операции через другие:

· ;

· ;

· ;

· ;

· ;

Замечание. Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание, или дизъюнкцию и отрицание. Дальнейшее исключение операций невозможно. Например, если использовать только конъюнкцию, то уже такая простая формула, как не может быть выражена с помощью операции конъюнкции.

Существуют операции, с помощью которых может быть выражена любая из 5 логических операций:

1) Связка Шеффера – дизъюнкция отрицаний.

Обозначение. x | y ≡ (« x не совместно с y »).

Логические значения связки Шеффера описываются следующей таблицей истинности:

2) Связка Лукасевича – конъюнкция отрицаний.

Логические значения связки Лукасевича описываются следующей таблицей истинности:

2. Равносильности, выражающие основные законы алгебры логики:

· – коммутативность конъюнкции;

· – коммутативность дизъюнкции;

· – ассоциативность конъюнкции;

· – ассоциативность дизъюнкции;

· – дистрибутивность конъюнкции относительно дизъюнкции;

· – дистрибутивность дизъюнкции относительно конъюнкции.

Замечание. Равносильности группы 3 показывают, что над формулами алгебры логики можно проводить те же преобразования, что и в алгебре чисел.

Равносильные преобразования формул

Используя равносильности групп 1–3 можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.

Источник