Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование

Текущая версия на 18:21, 22 февраля 2009

Шаблон:Campus

[править] Содержательное обобщение изученного материала

[править] Элементарные высказывания

Основным объектом изучения математической логики являются элементарные высказывания. Под термином "высказывание" мы будем понимать повествовательное предложение. При этом нас будет интересовать не построение: подлежащее - сказуемое - дополнение, а характерные свойства рассматриваемых образований: являются они истинными или ложными. Высказывания отличаются от других языковых образований тем, что мы можем присвоить им определенное значение истинности - "истина", если они истинны, значение "ложь", если они ложны. При этом мы исходим из "принципа исключенного третьего", или "третьего не дано", который состоит в том, что каждое высказывание или истинно, или ложно, и других возможностей нет. Ситуация, когда ни истинно, ни ложно, была бы и в обычном смысле неразрешимой. Этот принцип называют принципом двузначности. Все научные знания (законы и явления физики, химии и биологии, математические теоремы и т.д.), события повседневной жизни, ситуации, возникающие в процессах управления, формулируются в виде высказываний.

Примерами указанных высказываний являются:

"36 делится на 6", "Москва - столица России".

Все они имеют значение истинности "истина".

Следующие высказывания имеют значение истинности "ложь":

"Мышь больше слона",

"Молодые лошади называются щенятами",

"6 больше 8".

Повелительные ("Войдите, пожалуйста!"), вопросительные ("Знаешь ли ты информатику?") и бессмысленные предложения не являются высказываниями.

Если логика имеет дело со смыслом высказываний, то в алгебре логики работают с формулами.

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

Итак, в алгебре логики в каждом высказывании мы будем отвлекаться от всех особенностей высказывания, кроме одного - истинно оно или ложно. Истинное высказывание условно обозначается единицей (если x1 - высказывание " 36 делится на 6", то x1 = 1), а ложное - нулем (если x2 - высказывание "мышь больше слона", то x2 = 0).

Таким образом, диапазон изменения переменного - xi в алгебре логики существенно меньше, чем изменение переменного в элементарной алгебре: оно принимает только одно из двух значений - или 1, или 0.

[править] Логические операции

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

В алгебре логики основными (элементарными) операциями являются:

• отрицание,
• логическое сложение (дизъюнкция),
• логическое умножение (конъюнкция),
• импликация,
• эквивалентность.

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

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

[править] Основные соотношения

0 •0 = 0,	0 \/ 0 = 0,
0 • 1 = 0,	0 \/ 1 = 0,
1 • 0 = 0,	1 \/ 0 = 0,
1 • 1 = 1,	1 \/ 1 = 1,

[править] Основные тождества

X • 0 = 0,	X \/ 0 = X,
X • 1 = X,	X \/ 1 = 1,
,	,
X • X •...• X = X ,	X \/ X \/...\/ X = X,

[править] Сложное высказывание

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

Элементарные логические операции позволяют строить сложные (составные) высказывания на основе заданных высказываний.

Пусть X1, X2, X3, X4 - переменные высказывания (логические переменные), тогда следующие высказывания:

,

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

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

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

и

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

[править] Логические переменные и логические функции

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

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

Преобразование формулы происходит так: исходная формула или ее часть F1 заменяется другой, в результате получается новая формула F2, которая эквивалентна F1 (т.е. при любых значениях аргументов F1 и F2 дают один и тот же результат). Преобразование выражений производится на основе законов арифметики, а также полученных из них соотношений.

По аналогии строится алгебра логики. Она рассматривает логические выражения как алгебраические, которые можно преобразовать по определенным правилам. Разница заключается в том, что в выражениях алгебры логики переменные являются логическими (0 и 1). Знаки операций обозначают логические операции (логические связки).

Логической функцией называется функция f (X1,X2,...,Xn ) , которая, так же как и ее аргументы, может принимать только два значения (0 и 1). Совокупность значений аргументов будем называть набором.

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

[править] Материал для изучения

[править] Рекомендуемые ссылки

[править] Список литературы

К разделу Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики

Назад к разделу Вики-учебник для подготовки к ЕГЭ/Раздел Информатика