Propositional Formulas in CNF - Syntax Flashcards
What is a propositional variable?
A basic building block in propositional logic also called atom or atomic proposition. They are denoted by lowercase letters (possibly with subscripts) or expressive names like ‘inviteAlice’.
What are truth constants?
Two special symbols in propositional logic: ⊤ (Top) and ⊥ (Bottom). They are fundamental building blocks along with propositional variables.
What is a literal?
A literal is either:
1) a variable,
2) a truth constant,
3) a negated variable, or
4) a negated truth constant. Literals are often denoted by letters l, k, etc.
How is negation of a literal handled?
If a literal is x, then ¬x is its negation. If a literal is ¬x, then x is its negation. Similar rules apply to truth constants.
f a literal 𝑙 is 𝑥
, then ¬𝑙 is …?
¬𝑥
If a literal 𝑙 is ¬𝑥
, then ¬𝑙 is …?
𝑥
What does ¬¬𝑥 simplifies to?
𝑥
What is a clause?
A clause is a disjunction (OR) of literals. Each clause has a finite number of literals. For example: (x ∨ y) contains two literals.
What is an empty clause?
A clause containing zero literals, written as ⊥ or ∅
What is a unary clause?
A clause of size one, containing a single literal. Examples: (¬⊥), (x), (¬z)
What is a binary clause?
A clause of size two, containing two literals. Example: (x ∨ y)
What is a ternary clause?
A clause of size three, containing three literals. Example: (x ∨ y ∨ ¬z)
How many literals does the clause (𝑥∨𝑦) contain?
the clause (𝑥∨𝑦)
contains two literals (it is of size 2)
How many literals does the clause (¬⊥∨𝑥∨𝑎∨⊤∨¬𝑥) contain?
the clause (¬⊥∨𝑥∨𝑎∨⊤∨¬𝑥)
contains five literals (it is of size 5).
What symbols (possibly with a subscript) are usually used to denote formulas?
The symbols 𝐶,𝐷 (possibly with a subscript) are usually used
to denote formulas.
What is a formula?
A formula is a conjunction of clauses.
What is a formula in conjunctive normal form?
A conjunction (AND) of clauses. Can contain zero or more clauses.
What is an empty formula?
A formula that consists of zero clauses, denoted as ⊤
How can a clause of size n be written alternatively?
For a clause (l₁ ∨ … ∨ lₙ), it can be written as ⋁ₙᵢ₌₁ lᵢ
How can a formula of size n be written alternatively?
For a formula (C₁ ∧ … ∧ Cₙ), it can be written as ⋀𝑛𝑖=1𝐶𝑖
What are some alternative notations for Top (⊤)?
1, true, t
What are some alternative notations for Bottom (⊥)?
0, false, f
What are some alternative notations for disjunction (∨)?
e.g.
𝑘∨𝑙
||, +, OR
e.g.
𝑙∥𝑘,𝑙+𝑘,𝑙 OR 𝑘
What are some alternative notations for conjunction (∧)?
e.g. 𝐶∧𝐷
&&, *, AND
e.g.
𝐶 && 𝐷,𝐶∗𝐷,𝐶 AND 𝐷
What are some alternative notations for negation (¬)?
e.g.
¬𝑥
!, ̄, NOT, -
e.g.
!𝑥,𝑥⎯⎯⎯,−𝑥,NOT𝑥
What symbols are commonly used to denote formulas?
φ, ψ (possibly with subscripts)
What symbols are commonly used to denote clauses?
C, D (possibly with subscripts)
What is important to note about propositional logic syntax?
There is no standard syntax - different books or articles may use different symbols based on their application domain (e.g., mathematicians vs electrical engineers use different notation)
