Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование
(→Содержательное обобщение изученного материала) |
|||
(не показаны 12 промежуточных версий 1 участника) | |||
Строка 1: | Строка 1: | ||
+ | {{шаблон:campus}} | ||
== Содержательное обобщение изученного материала == | == Содержательное обобщение изученного материала == | ||
+ | |||
+ | ===Элементарные высказывания=== | ||
Основным объектом изучения математической логики являются элементарные высказывания. | Основным объектом изучения математической логики являются элементарные высказывания. | ||
− | Под термином "высказывание" мы будем понимать повествовательное предложение. При этом нас будет интересовать не построение: подлежащее - сказуемое - дополнение, а характерные свойства рассматриваемых образований: являются они истинными или ложными. | + | Под термином "''высказывание''" мы будем понимать повествовательное предложение. При этом нас будет интересовать не построение: подлежащее - сказуемое - дополнение, а характерные свойства рассматриваемых образований: являются они истинными или ложными. |
− | Высказывания отличаются от других языковых образований тем, что мы можем присвоить им определенное значение истинности - "истина", если они истинны, значение "ложь", если они ложны. При этом мы исходим из "принципа исключенного третьего", или "третьего не дано", который состоит в том, что каждое высказывание или истинно, или ложно, и других возможностей нет. Ситуация, когда ни истинно, ни ложно, была бы и в обычном смысле неразрешимой. Этот принцип называют принципом двузначности. | + | Высказывания отличаются от других языковых образований тем, что мы можем присвоить им определенное значение истинности - "'''истина'''", если они истинны, значение "'''ложь'''", если они ложны. При этом мы исходим из "''принципа исключенного третьего''", или "''третьего не дано''", который состоит в том, что каждое высказывание или истинно, или ложно, и других возможностей нет. Ситуация, когда ни истинно, ни ложно, была бы и в обычном смысле неразрешимой. Этот принцип называют принципом двузначности. |
Все научные знания (законы и явления физики, химии и биологии, математические теоремы и т.д.), события повседневной жизни, ситуации, возникающие в процессах управления, формулируются в виде высказываний. | Все научные знания (законы и явления физики, химии и биологии, математические теоремы и т.д.), события повседневной жизни, ситуации, возникающие в процессах управления, формулируются в виде высказываний. | ||
Примерами указанных высказываний являются: | Примерами указанных высказываний являются: | ||
− | " | + | "36 делится на 6", |
"Москва - столица России". | "Москва - столица России". | ||
− | Все они имеют значение истинности "истина". | + | |
+ | Все они имеют значение истинности "'''истина'''". | ||
+ | |||
Следующие высказывания имеют значение истинности "ложь": | Следующие высказывания имеют значение истинности "ложь": | ||
+ | |||
"Мышь больше слона", | "Мышь больше слона", | ||
+ | |||
"Молодые лошади называются щенятами", | "Молодые лошади называются щенятами", | ||
+ | |||
"6 больше 8". | "6 больше 8". | ||
+ | |||
Повелительные ("Войдите, пожалуйста!"), вопросительные ("Знаешь ли ты информатику?") и бессмысленные предложения не являются высказываниями. | Повелительные ("Войдите, пожалуйста!"), вопросительные ("Знаешь ли ты информатику?") и бессмысленные предложения не являются высказываниями. | ||
− | Если логика имеет дело со смыслом высказываний, то в алгебре логики работают с формулами. Любое элементарное высказывание обозначается малой буквой латинского алфавита | + | Если логика имеет дело со смыслом высказываний, то в алгебре логики работают с формулами. |
+ | |||
+ | Любое элементарное высказывание обозначается малой буквой латинского алфавита, совершенно так же, как в элементарной алгебре обозначаются величины, когда мы абстрагируемся от того, какие именно предметы изучаются, нас интересует только их количество и соотношение между ними. | ||
Поскольку высказывание может принимать одно из двух значений, то говорят о "переменных высказываниях". Это означает, что рассматривается не только конкретно определенное высказывание хi , но также некоторая логическая переменная х i , которую можно использовать для обозначения произвольного высказывания. Замещение переменной конкретным высказыванием означает предоставления одного из значений "истина" или "ложь". | Поскольку высказывание может принимать одно из двух значений, то говорят о "переменных высказываниях". Это означает, что рассматривается не только конкретно определенное высказывание хi , но также некоторая логическая переменная х i , которую можно использовать для обозначения произвольного высказывания. Замещение переменной конкретным высказыванием означает предоставления одного из значений "истина" или "ложь". | ||
− | Итак, в алгебре логики в каждом высказывании мы будем отвлекаться от всех особенностей высказывания, кроме одного - истинно оно или ложно. Истинное высказывание условно обозначается единицей (если x1 - высказывание " | + | Итак, в алгебре логики в каждом высказывании мы будем отвлекаться от всех особенностей высказывания, кроме одного - истинно оно или ложно. Истинное высказывание условно обозначается единицей (если x1 - высказывание " 36 делится на 6", то x1 = 1), а ложное - нулем (если x2 - высказывание "мышь больше слона", то x2 = 0). |
Таким образом, диапазон изменения переменного - xi в алгебре логики существенно меньше, чем изменение переменного в элементарной алгебре: оно принимает только одно из двух значений - или 1, или 0. | Таким образом, диапазон изменения переменного - xi в алгебре логики существенно меньше, чем изменение переменного в элементарной алгебре: оно принимает только одно из двух значений - или 1, или 0. | ||
− | + | ||
+ | ===Логические операции=== | ||
+ | |||
Из элементарных высказываний с помощью логических связок " и", "или", "не", "если : то" и других (логических операций) строятся сложные высказывания - формулы (или функции ) алгебры логики. | Из элементарных высказываний с помощью логических связок " и", "или", "не", "если : то" и других (логических операций) строятся сложные высказывания - формулы (или функции ) алгебры логики. | ||
− | Способы построения новых высказываний из заданных с помощью логических связок, их преобразования и установления истинности изучаются в логике высказываний с помощью алгебраических методов. | + | |
+ | В алгебре логики основными (элементарными) операциями являются: | ||
+ | *[[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование/Отрицание|отрицание]], | ||
+ | *[[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование/Дизъюнкция|логическое сложение (дизъюнкция), ]] | ||
+ | *[[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование/Конъюнкция|логическое умножение (конъюнкция), ]] | ||
+ | *[[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование/Импликация|импликация,]] | ||
+ | *[[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики/Логические выражения и их преобразование/Эквивалентность|эквивалентность. | ||
+ | ]] | ||
+ | |||
+ | Способы построения новых высказываний из заданных с помощью логических связок, их преобразования и установления истинности изучаются в логике высказываний с помощью алгебраических методов. | ||
+ | |||
+ | [http://school-collection.edu.ru/catalog/res/9e997f40-f285-4369-aa7d-88b892beca45/?from=a30a9550-6a62-11da-8cd6-0800200c9a66& Элементарные логические операции. Демонстрация к лекции. Интерактивное средство для самостоятельной работы учащихся] | ||
+ | |||
+ | ===Основные соотношения=== | ||
+ | |||
+ | {| border="1" | ||
+ | |- | ||
+ | ! 0 •0 = 0, | ||
+ | ! 0 \/ 0 = 0, | ||
+ | ! | ||
+ | |- | ||
+ | ! 0 • 1 = 0, | ||
+ | ! 0 \/ 1 = 0, | ||
+ | ! | ||
+ | |- | ||
+ | ! 1 • 0 = 0, | ||
+ | ! 1 \/ 0 = 0, | ||
+ | ! [[Изображение:EGL1.jpg]] | ||
+ | |- | ||
+ | ! 1 • 1 = 1, | ||
+ | ! 1 \/ 1 = 1, | ||
+ | ! [[Изображение:EGL2.jpg]] | ||
+ | |} | ||
+ | |||
+ | ===Основные тождества=== | ||
+ | |||
+ | {| border="1" | ||
+ | |- | ||
+ | ! X • 0 = 0, | ||
+ | ! X \/ 0 = X, | ||
+ | ! | ||
+ | |- | ||
+ | ! X • 1 = X, | ||
+ | ! X \/ 1 = 1, | ||
+ | ! | ||
+ | |- | ||
+ | ! [[Изображение:EGL3.jpg]], | ||
+ | ! [[Изображение:EGL4.jpg]], | ||
+ | ! | ||
+ | |- | ||
+ | ! X • X •...• X = X , | ||
+ | ! X \/ X \/...\/ X = X, | ||
+ | ! [[Изображение:EGL5.jpg]] | ||
+ | |} | ||
+ | |||
+ | ===Сложное высказывание=== | ||
+ | |||
+ | В логических задачах исходными данными являются суждения, подчас неожиданные и нередко весьма запутанные. Высказывания и связи между ними бывают иногда столь противоречивыми, что такие "твердые орешки" не под силу "раскусить" и вдумчивому математику. | ||
+ | В данных случаях большую помощь может оказать ЭВМ как необходимый инструмент эффективного решения логических задач с многими переменными. В настоящее время нет ни одного языка программирования, который не включал бы логических операций. | ||
+ | |||
+ | Элементарные логические операции позволяют строить сложные (составные) высказывания на основе заданных высказываний. | ||
+ | |||
+ | Пусть '''X1''', '''X2''', '''X3''', '''X4''' - переменные высказывания (логические переменные), тогда следующие высказывания: | ||
+ | |||
+ | [[Изображение:EGG1.jpg]], | ||
+ | |||
+ | представляют формулы алгебры высказываний. | ||
+ | |||
+ | Так же, как и в алгебре арифметики, в алгебре логики устанавливается приоритет выполнения логических операций. Они упорядочены в следующей последовательности: | ||
+ | |||
+ | [[Изображение:EGG2.jpg]] | ||
+ | При этом отрицание является наиболее сильной операцией, эквивалентность - самой слабой. С учетом указанного порядка две формулы: | ||
+ | |||
+ | [[Изображение:EGG3.jpg]] | ||
+ | |||
+ | и | ||
+ | |||
+ | [[Изображение:EGG4.jpg]] | ||
+ | |||
+ | имеют одинаковые значения. Истинность составных высказываний (логических формул), образованных в результате выполнения логических операций над простыми высказываниями, зависит от истинности исходных высказываний. Для того, чтобы иметь возможность вычислять значения истинности этих высказываний, определим базовое понятие - '''''логическую функцию'''''. | ||
+ | |||
+ | ===Логические переменные и логические функции=== | ||
+ | |||
Сущность алгебраического подхода к логике поясним на примере элементарной алгебры - алгебры арифметики. Основные объекты алгебры арифметики - выражения (формулы), состоящие из букв, знаков операций и скобок. С формулами производят процедуры двух типов: вычисления и преобразования. | Сущность алгебраического подхода к логике поясним на примере элементарной алгебры - алгебры арифметики. Основные объекты алгебры арифметики - выражения (формулы), состоящие из букв, знаков операций и скобок. С формулами производят процедуры двух типов: вычисления и преобразования. | ||
Вычисления - вместо букв подставляют числа, знаки указывают действия, а скобки их порядок. Каждая формула задает функцию. Переменные - буквы формулы. | Вычисления - вместо букв подставляют числа, знаки указывают действия, а скобки их порядок. Каждая формула задает функцию. Переменные - буквы формулы. | ||
− | Преобразование формулы происходит так: исходная формула или ее часть F1 заменяется другой, в результате получается новая формула F2, которая эквивалентна F1 (т.е. при любых значениях аргументов F1 и F2 дают один и тот же результат). Преобразование выражений производится на основе законов арифметики, а также полученных из них соотношений | + | Преобразование формулы происходит так: исходная формула или ее часть F1 заменяется другой, в результате получается новая формула F2, которая эквивалентна F1 (т.е. при любых значениях аргументов F1 и F2 дают один и тот же результат). Преобразование выражений производится на основе законов арифметики, а также полученных из них соотношений. |
+ | |||
По аналогии строится алгебра логики. Она рассматривает логические выражения как алгебраические, которые можно преобразовать по определенным правилам. Разница заключается в том, что в выражениях алгебры логики переменные являются логическими (0 и 1). Знаки операций обозначают логические операции (логические связки). | По аналогии строится алгебра логики. Она рассматривает логические выражения как алгебраические, которые можно преобразовать по определенным правилам. Разница заключается в том, что в выражениях алгебры логики переменные являются логическими (0 и 1). Знаки операций обозначают логические операции (логические связки). | ||
− | + | ||
− | + | '''''Логической функцией''''' называется функция f ('''X1,X2,...,Xn''' ) , которая, так же как и ее аргументы, может принимать только два значения (0 и 1). Совокупность значений аргументов будем называть ''набором''. | |
− | + | ||
+ | Любую логическую функцию можно задать таблицей истинности, в левой части которой вписаны все возможные наборы значений ее аргументов '''X1,X2,...,Xn''' , а правая часть - столбец значений функции, соответствующих этим наборам: | ||
+ | |||
+ | {| border="1" | ||
+ | |- | ||
+ | ! № набора | ||
+ | ! X1,X2,...,Xn | ||
+ | ! f(X1,X2,...,Xn) | ||
+ | |- | ||
+ | | 0 | ||
+ | | Набор значений аргументов | ||
+ | | Значение функции (0 или 1) | ||
+ | |- | ||
+ | | 1 | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | | ... | ||
+ | | | ||
+ | | | ||
+ | |- | ||
+ | | 2<sup>n</sup> - 1 | ||
+ | | | ||
+ | | | ||
+ | |} | ||
== Материал для изучения == | == Материал для изучения == | ||
Строка 43: | Строка 163: | ||
== Список литературы== | == Список литературы== | ||
+ | [[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики|К разделу '''Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики''']] | ||
[[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика|''Назад к разделу'' '''Вики-учебник для подготовки к ЕГЭ/Раздел Информатика''']] | [[Вики-учебник для подготовки к ЕГЭ/Раздел Информатика|''Назад к разделу'' '''Вики-учебник для подготовки к ЕГЭ/Раздел Информатика''']] |
Текущая версия на 18:21, 22 февраля 2009
Содержание |
[править] Содержательное обобщение изученного материала
[править] Элементарные высказывания
Основным объектом изучения математической логики являются элементарные высказывания. Под термином "высказывание" мы будем понимать повествовательное предложение. При этом нас будет интересовать не построение: подлежащее - сказуемое - дополнение, а характерные свойства рассматриваемых образований: являются они истинными или ложными. Высказывания отличаются от других языковых образований тем, что мы можем присвоить им определенное значение истинности - "истина", если они истинны, значение "ложь", если они ложны. При этом мы исходим из "принципа исключенного третьего", или "третьего не дано", который состоит в том, что каждое высказывание или истинно, или ложно, и других возможностей нет. Ситуация, когда ни истинно, ни ложно, была бы и в обычном смысле неразрешимой. Этот принцип называют принципом двузначности. Все научные знания (законы и явления физики, химии и биологии, математические теоремы и т.д.), события повседневной жизни, ситуации, возникающие в процессах управления, формулируются в виде высказываний.
Примерами указанных высказываний являются:
"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 , а правая часть - столбец значений функции, соответствующих этим наборам:
№ набора | X1,X2,...,Xn | f(X1,X2,...,Xn) |
---|---|---|
0 | Набор значений аргументов | Значение функции (0 или 1) |
1 | ||
... | ||
2n - 1 |
[править] Материал для изучения
[править] Рекомендуемые ссылки
[править] Список литературы
К разделу Вики-учебник для подготовки к ЕГЭ/Раздел Информатика/Основы логики
Назад к разделу Вики-учебник для подготовки к ЕГЭ/Раздел Информатика