tag

#propositional logic

6 pages tagged

Maths › 03. Logic and Foundations ›

1.4 Normal Forms

Normal forms are standard shapes for propositional formulas, and they are useful because they make formulas easier to compare, transform, and process by algorithms. Literals and Clauses A literal is either a propositional variable or the negation of a propositional variable. Thus the following are literals: $$ p, \quad ¬p, \quad q, \quad ¬q $$ The formula: $$ ¬(p \land q) $$ is not a literal, because the negation is...
logic propositional logic normal forms CNF DNF May 2, 2026
Maths › 03. Logic and Foundations ›

1.5 Soundness and Completeness

Propositional logic can be studied in two complementary ways. The semantic approach studies truth under valuations, while the proof theoretic approach studies formal derivations from axioms and inference rules. Soundness and completeness explain how these two approaches are related. Semantic Consequence Let $\Gamma$ be a set of formulas, and let $A$ be a formula. We say that $A$ is a semantic consequence of $\Gamma$ if every valuation that makes all...
logic propositional logic proof theory soundness completeness May 2, 2026
Maths › 03. Logic and Foundations ›

1.2 Semantics

Semantics assigns meaning to the formulas of propositional logic by assigning truth values to propositional variables and then extending this assignment to all formulas according to the logical connectives. Truth Values We use two truth values: $$ \mathrm{T} $$ and: $$ \mathrm{F} $$ The value $\mathrm{T}$ means true, and the value $\mathrm{F}$ means false, and every formula in classical propositional logic will receive exactly one of these two values once...
logic propositional logic semantics truth tables May 2, 2026
Maths › 03. Logic and Foundations ›

1.3 Equivalence

Logical equivalence compares formulas by their truth values under all valuations, rather than by their written form, and it gives a precise way to say that two formulas express the same logical content. Definition 1.17 (Logical Equivalence) Let $A$ and $B$ be formulas. We say that $A$ and $B$ are logically equivalent if: $$ v(A)=v(B) $$ for every valuation $v$. In this case we write: $$ A \equiv B $$...
logic propositional logic equivalence boolean algebra May 2, 2026
Maths › 03. Logic and Foundations ›

1. Propositional Logic

Propositional logic studies reasoning with statements that can be either true or false, and it provides a formal language together with precise rules that allow such reasoning to be carried out in a systematic and verifiable way, independent of the specific meaning of the statements involved. The basic objects of study are propositional variables, which serve as placeholders for statements, and these variables are combined using logical connectives to form...
logic propositional logic foundations May 2, 2026
Maths › 03. Logic and Foundations ›

1.1 Syntax

We define the formal language of propositional logic by specifying an alphabet of symbols together with precise rules that determine which expressions are well formed formulas, and this definition is inductive in the sense that every formula is constructed from simpler formulas in a finite number of steps, which ensures that the structure of formulas can always be analyzed in a systematic way. Alphabet The alphabet consists of propositional variables,...
logic propositional logic syntax formulas May 2, 2026