Алгебра логики высказываний Основные понятия
жүктеу/скачать 0.9 Mb.
|
Алгебра логики высказыванийОсновные понятияИсходным понятием логики высказываний является простое высказывание. Это понятие не определяется через другие понятия, так как является базовым. Под высказыванием обычно понимают всякое повествовательно предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание называют истинным. В противном случае – ложным. Обычно элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными. Истинные значения обозначаются буквой И или 1, а ложные – Л или 0. Из элементарных высказываний можно составить более сложные с помощью логических связок , , , , , называемых соответственно отрицание, логическое и (конъюнкция), логическое или (дизъюнкция), логическое следствие (импликация), эквивалентность и круглых скобок (, ). Семантику логических связок можно представить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных. В правой части – соответствующие им значения новых выражений, полученных из переменных и связок.
Связки имеют следующий приоритет: . Приоритет операций, представленных логическими связками можно изменить с помощью скобок. Высказывания, построенные с помощью простых высказываний, связок и скобок, называют правильно построенными формулами или сокращённо формулами. Замечательным свойством логики высказываний является то, что ее семантика близка к соответствующим высказываниям на естественном языке. Так, например семантика формул содержащих связки и практически совпадает со смыслом фраз содержащих слова «не» и «и». Однако имеются и некоторые различия. Так формула х у несколько шире, чем русское «х или у». Выражение «х или у» по смыслу ближе к формуле х у х у. Еще больше различий между семантикой формулы х у в логике высказываний и выражению «из х следует у». В русском языке это выражение истинно, если истинны х и у, т.е. предложение русского языка по смыслу совпадает с формулой х у. Логическое следствие истинно также, если х и у ложны или х ложна, а у истинна. Логическую формулу х у следует интерпретировать на естественном языке так: «Если х истинна, то у тоже истинна, а остальное неизвестно». Для любой формулы также можно построить таблицу истинности. Например, для формулы таблица истинности будет выглядеть следующим образом:
Очевидно, что если формула содержит n переменных, то в таблице истинности будет содержаться 2n строк. В приведенном примере формула содержит 2 переменные и 22 = 4 строки. Кроме того, данная формула истинна на любом наборе значений своих переменных. Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы будем обозначать знаком равенства =. жүктеу/скачать 0.9 Mb. Достарыңызбен бөлісу:
|