Литерал
Литерал — это логическая переменная или её отрицание. Литералы служат составными элементами нормальных форм булевых функций.
Логическая переменная принимает одно из двух значений: 0 или 1. Если переменная \(x=1\), то литерал \(x\) имеет значение 1, а литерал \(\neg x\) — значение 0. Если \(x=0\), значения меняются местами. Поэтому литералы \(x\) и \(\neg x\) всегда противоположны.
Как записывают литералы
В записи булевых выражений литерал может входить в конъюнкцию или дизъюнкцию. Например, в выражении \((x \land \neg y) \lor z\) три литерала: \(x\), \(\neg y\) и \(z\). Здесь \(x\) и \(z\) — положительные литералы, а \(\neg y\) — отрицательный литерал.
Рассмотрим выражение \(\neg a \lor (b \land c)\). Его литералы: \(\neg a\), \(b\) и \(c\). Скобки и знаки \(\lor\), \(\land\) литералами не являются: они показывают, как литералы соединяются.
Литерал — не любая часть логического выражения. Например, \(a \land b\) — это конъюнкция двух литералов, а \(a \lor \neg b\) — дизъюнкция двух литералов. Сама логическая переменная является литералом, но выражение с операцией уже обычно называют логической формулой.
В дизъюнктивной нормальной форме литералы объединяются конъюнкциями, а получившиеся конъюнкции — дизъюнкциями. В конъюнктивной нормальной форме порядок операций обратный: дизъюнкции литералов объединяются конъюнкциями. Поэтому при преобразовании выражения важно уметь быстро находить все литералы.
Сколько литералов в выражении \((p \lor \neg q) \land r\)?
Главное
- Литерал — это логическая переменная или её отрицание.
- У переменной \(x\) два литерала: \(x\) и \(\neg x\).
- Литералы являются элементами конъюнкций и дизъюнкций в нормальных формах.