1. Высказывания, формулы, тавтологии
Определение. Высказыванием называется утверждение, которое является истинным или ложным (но не одновременно).
То есть, чтобы выяснить, является ли некоторое предложение высказыванием, нужно сначала убедиться, что это утверждение, а затем установить, истинно оно или ложно.
Пример. “Москва – столица России” – истинное высказывание.
“5 –четное число” – ложное высказывание.
“
” – не высказывание (неизвестно, какие значения принимает 
).
“Студент второго курса” не высказывание (не является утверждением).
Высказывания бывают элементарные и составные.
Элементарные высказывания не могут быть выражены через другие высказывания. Составные высказывания можно выразить с помощью элементарных высказываний.
Пример. “Число 22 четное” – элементарное высказывание.
“Число 22 четное и делится на 11” – составное высказывание.
Высказывания обозначают заглавными буквами латинского алфавита: 
, 
, 
,… Эти буквы называют логическими Атомами.
При фиксированном множестве букв 
Интерпретацией называется функция 
, которая отображает множество 
во множество истинностных (логических) значений 
, то есть 
.
Истинностные значения истина и ложь сокращенно обозначаются и, л или T, F, или 1,0. Мы будем использовать обозначения 1 и 0. В определенной интерпретации буквы принимают значения 1 или 0.
К высказываниям и буквам можно применять известные из курса дискретной математики логические связки или логические операции. При этом получаются Формулы (формы). Формулы становятся высказываниями при подстановке всех значений букв.
Таблицы истинности основных логических операций.
Более строго формула определяется так.
Определение. 1) Всякая буква есть формула.
2) Если , — формулы, то формулами являются также , 
, 
, 
, 
.
3) Символ является формулой тогда и только тогда, когда это следует из 1) и 2).
В классической логике формулы принято заключать в круглые скобки, но в мы этого делать не будем. Для всякой формулы можно построить таблицу истинности.
Значение формулы 
в заданной интерпретации обозначают 
(или 
, или 
).
Часть формулы, которая сама является формулой, называется Подформулой данной формулы.
Определение. Формула называется Тавтологией, если она принимает только истинные значения при любых значениях букв.
Другими словами, тавтология – это тождественно истинная формула.
Установить, является ли формула тавтологией, можно:
– по таблице истинности,
– используя свойства логических операций.
Из курса дискретной математики известны основные логические эквивалентности (свойства логических операций), которые являются примерами тавтологий.
1. Коммутативность: 
, 
.
, 
.
, 
.
4. Идемпотентность: 
, 
.
5. Закон двойного отрицания: 
.
6. Закон исключения третьего: 
.
7. Закон противоречия: 
.
8. Законы де Моргана:
, 
.
9. Свойства операций с логическими константами:
, 
, 
, 
.
Здесь , и – любые буквы.
Примеры. 1. Доказать, что формула 
является тавтологией.
Доказательство. Допустим, что при некоторых значениях букв (то есть в некоторой интерпретации)
Приходим к противоречию, которое доказывает, что исходная формула – тавтология.
2. Доказать, что формула 
является тавтологией.
Доказательство. Эквиваленция истинна, если левая и правая части принимают одинаковые значения на некотором наборе значений букв.
Допустим, что при некоторых значениях букв
Следовательно, исходная формула – тавтология.
3. Доказать, что формула 
является тавтологией.
Доказательство. Допустим, что при некоторых значениях букв
Следовательно, исходная формула – тавтология.
Таким образом, тождественную истинность импликации удобно доказывать от противного, а тождественную истинность эквиваленции установлением равенства значений левой и правой части.
Теорема. Пусть формулы и – тавтологии. Тогда формула – тавтология.
Доказательство. Пусть 
, 
, …, 
– буквы в формулах и . В теории булевых функций было доказано, что все булевы функции, а, следовательно, и формулы, можно считать зависящими от одного и того же количества букв. Рассмотрим некоторый набор значений 
, 
, …, 
, где 
, 
. Подставим данный набор значений в формулы и вместо соответствующих букв. Формулы являются тавтологиями по условию теоремы, следовательно, 
и 
. По таблице истинности импликации получаем, что . Поскольку набор значений , , …, был произволен, формула – тавтология, что и требовалось доказать.
Теорема. Пусть формула – тавтология, , , …, 
– буквы в формуле , 
, 
, …, 
– любые формулы. Тогда новая формула 
– тавтология.
Доказать, что формула является тавтологией, используя равносильность формул
Используя равносильные преобразования доказать, что формула является тавтологией
Используя равносильные преобразования доказать, что формула является тавтологией: F(X,Y,Z) = ((Y.
Сообщение от Zlatta
Вы много знаете этих равносильностей? В частности, равносильность, выражающую импликацию через другие операции. Почему бы ее не применить?
См. учебник булевой алгебры или пособие, рекомендованное вашим преподавателем.
Сообщение было отмечено VSI как решение
Решение
Используя равносильные преобразования, доказать, что формула является тавтологией
F(X, Y) =(Y^(Y->X)) — >X ПОМОГИТЕ ПОЖАЛУЙСТА
Доказать, что формула является тавтологией
Доказать, что формула является тавтологией F=¬(А->¬( B&A))->AVB с помощью эквивалентных.
Доказать, что формула является тавтологией
Нужно доказать, что данная формула является тавтологией: (А => (B => C)) => ((A =>B) => (A =>C)).
Производя равносильные преобразования, доказать, что формула является тавтологией
Я пометил ! знаком — отрицание. (p \vee r)\wedge (q\vee r) <-> (!p\vee !q->r) Сам до конца не.
Доказать, что формула является тавтологией без построения таблицы истинности.
Добрый день! Подскажите как решить. Доказать, что формула является тавтологией без построения.
Доказать, что формула является тавтологией без построения таблицы истиности
Прошу помочь решить и расписать по возможности подробно. Доказать, что формула является.
Доказать, что формула является тавтологией без построения таблицы истинности
Добрый день! Подскажите как решить. Доказать, что формула является тавтологией без построения.
Тавтология и противоречие. Равносильность высказываний
Формула х2,лгя) называется тавтологией или тождественно истиной формулой, если при любых значениях высказываний хх> х2,значение F= 1.
Например, рассмотрим формулу Л v -Д, соответствующую высказыванию «этот треугольник прямоугольный или косоугольный». Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный.
Тавтологии играют в логике особо важную роль как формулы, отражающие логическую структуру предложений, истинных в силу одной только этой структуры. Для доказательства того, что формула является тавтологией, достаточно построить таблицу истинности для нее. В этой таблице столбец под самой формулой должен состоять только из единиц.
Формула F(x 1, х2, . хп) называется противоречием или тождественно ложной формулой, если при любых значения высказываний х1у х2. хп значение F = 0.
Формула называется выполнимой, если существует такой набор значений переменных, при котором эта формула принимает значение 1. Формула называется опровержимой, если существует такой набор значений переменных, при котором эта формула принимает значение 0.
Пример 4.14. Рассмотрим формулу А & -Л, которой соответствует, например, высказывание «Катя — самая высокая девочка в классе, и в классе есть девочки выше Кати». Очевидно, что эта формула ложна, так как либо Л, либо ^Л обязательно ложно.
Пример 4.15. Выясним, является ли следующая формула тождественно истинной: F — [(Л —> В) & -‘В] —> -*Л.
Решение. Построим таблицу (табл. 4.13) истинности заданной формулы, используя определения логических операций.
Булевы функции. Равносильность. Тавтологии
Булевой функцией (по имени английского математика и логика Джорджа Буля) называется логическая функция, аргументы которой и она сама принимают два значения 0 и 1.
Если f(x1,…,xn) булева функция, зависящая от n аргументов, то она вполне определяется своими значениями для 2 n наборов значений аргументов. Кроме того, она вполне определяется подмножеством тех наборов, для которых она принимает значение 1. Поскольку число различных подмножеств равно 
, то
Теорема:Число различных булевых функций, зависящих от n аргументов равно .
Так, для n=2 число различных булевых функций равно 16. Очевидно, что всякая формула логики высказываний является булевой функцией. В дальнейшем будет показано, что и всякую булевую функцию можно интерпретировать как формулу логики высказываний.
Определение:Две формулы F и G называются равносильными, если они равны как булевы функции, т.е. принимают одинаковые значения при всех наборах значений простых компонент. Обозначается FºG.
Замечание: Формулы F и G могут содержать разные компоненты. При составлении таблицы истинности в набор включаются все компоненты, входящие в хотя бы одну из этих функций, т.е. некоторые простые компоненты могут быть фиктивными.
Тождественно-истинной (тавтологией) называется формула, таблица истинности которой состоит из одних 1 и тождественно-ложной, если все её значения равны 0. Обозначаются они соответственно Fº1 и Fº0. Если формула может принимать как значения 1, так и 0, то она называется выполнимой.
Пример:
В задаче 1 формулы b), c), d), e) — тождественно-истинные, формулы a) и f) — выполнимые.
Примером тождественно-ложной формулы будет ((aÚb)Ù(`aÙ`b)).
Отношение равносильности является отношением эквивалентности на множестве всех формул логики высказываний. Класс эквивалентности — это все формулы, соответствующие одной и той же булевой функции. Изучение булевых функций имеет большое значение как для алгебры и математической логики, так и для приложений в компьютерной математике и теории автоматов. Особую роль играют тавтологии. Проверить, является ли формула тавтологией или равносильны ли данные формулы, можно, составляя таблицы истинности. Процедура эта для большого числа аргументов утомительна или даже невозможна. Однако, существуют методы, позволяющие значительно упростить эту проверку.
Наша задача в дальнейшем состоит в установлении правил равносильного преобразования формул и приведение формулы к некоторому нормальному виду
Булевой формулой называется формула, не содержащая импликации и эквиваленций.
Теорема: Всякая формула логики высказываний равносильна булевой формуле.
Доказательство этой теоремы опирается на следующие равносильности a®bº`aÚbиa«bºabÚ`a`b
Они проверяются таблицей истинности:
| а | b | a®b | `aÚb | a«b | abÚ`a`b |
Эти равносильности имеют логический смысл.
Формула a®b означает: если верно а то верно b.
А формула `aÚb: или неверно а или верно b.
Это последнее высказывание и есть обоснование таблицы истинности для операции a®b.
Формула a«b переводится так: а верно тогда и только тогда, когда верно b, а формула abÚ`a`b означает или a и b одновременно верны , или одновременно неверны.
Сформулируем также два правила подстановки:
1. Пусть FA — формула, в которой фиксировано вхождение в неё формулы А ( в этом случае говорят, что формула А является частью формулы F , и что формула F длиннее формулы А) и пусть АºВ, тогда FА ºFВ, где в формуле F формула А заменена на формулу В.
Например F=(a®b)Ùc и A=a®b. Тогда A=a®bºB=`aÚb и (a®b)Ùcº(`aÚb)Ùc.
2. Пусть FаºGa, причём в формулах F и G фиксированы все вхождения простой компоненты а. Тогда FAºGA, где А — произвольная формула, и в формулах F и G простая компонента а заменена всюду на формулу А.
Пример. abÚ`a`bºa«b. Пусть А=c®d. Тогда (c®d)bÚ( 
)`bº(c®d)«b
Доказательство теоремы может быть проведено методом индукции по длине формулы с использованием указанных равносильностей, правил подстановки, а также таблицы основных равносильностей.