Logic for Computer Science

2.

Propositional Logic

2.1.

Foundations of Propositional Logic

2.1.1.

Propositions and Truth Values

2.1.1.1.

Definition of a Proposition

2.1.1.2.

Binary Truth Values

2.1.1.3.

Examples of Propositions

2.1.1.4.

Non-Propositions

2.1.2.

Atomic Propositions

2.1.2.1.

Identifying Atomic Statements

2.1.2.2.

Notation for Atomic Propositions

2.1.2.3.

Propositional Variables

2.1.3.

Compound Propositions

2.1.3.1.

Building Compound Statements

2.1.3.2.

Use of Logical Connectives

2.1.3.3.

Complexity of Compound Propositions

2.2.

Syntax of Propositional Logic

2.2.1.

Logical Connectives

2.2.1.1.

2.2.1.1.1.

Symbol and Usage

2.2.1.1.2.

Truth Table for Negation

2.2.1.1.3.

Properties of Negation

2.2.1.2.

2.2.1.2.1.

Symbol and Usage

2.2.1.2.2.

Truth Table for Conjunction

2.2.1.2.3.

Properties of Conjunction

2.2.1.3.

2.2.1.3.1.

Symbol and Usage

2.2.1.3.2.

Truth Table for Disjunction

2.2.1.3.3.

Inclusive vs Exclusive Disjunction

2.2.1.3.4.

Properties of Disjunction

2.2.1.4.

2.2.1.4.1.

Symbol and Usage

2.2.1.4.2.

Truth Table for Implication

2.2.1.4.3.

Material Conditional

2.2.1.4.4.

Common Misconceptions

2.2.1.4.5.

Properties of Implication

2.2.1.5.

2.2.1.5.1.

Symbol and Usage

2.2.1.5.2.

Truth Table for Biconditional

2.2.1.5.3.

Properties of Biconditional

2.2.2.

Well-Formed Formulas

2.2.2.1.

Definition of Well-Formed Formulas

2.2.2.2.

Rules for Constructing Well-Formed Formulas

2.2.2.3.

Parentheses and Grouping

2.2.2.4.

Parse Trees for Formulas

2.2.3.

Operator Precedence and Associativity

2.2.3.1.

Precedence Rules for Connectives

2.2.3.2.

Associativity Rules

2.2.3.3.

Disambiguating Expressions

2.2.3.4.

Fully Parenthesized Formulas

2.3.

Semantics of Propositional Logic

2.3.1.

2.3.1.1.

Constructing Truth Tables

2.3.1.2.

Evaluating Compound Propositions

2.3.1.3.

Truth Tables for Complex Formulas

2.3.1.4.

Computational Complexity of Truth Tables

2.3.2.

Valuations and Models

2.3.2.1.

Assigning Truth Values

2.3.2.2.

Satisfying Assignments

2.3.2.3.

Truth Assignments

2.3.3.

Logical Equivalence

2.3.3.1.

Definition of Logical Equivalence

2.3.3.2.

Testing for Logical Equivalence

2.3.3.3.

Important Equivalences

2.3.3.3.1.

De Morgan's Laws

2.3.3.3.2.

Distributive Laws

2.3.3.3.3.

Commutative Laws

2.3.3.3.4.

Associative Laws

2.3.3.3.5.

Double Negation Law

2.3.3.3.6.

2.3.3.3.7.

Domination Laws

2.3.3.3.8.

Absorption Laws

2.3.3.3.9.

Implication Equivalences

2.3.3.3.10.

Biconditional Equivalences

2.3.4.

Tautologies, Contradictions, and Contingencies

2.3.4.1.

Identifying Tautologies

2.3.4.2.

Identifying Contradictions

2.3.4.3.

Identifying Contingencies

2.3.4.4.

Examples and Applications

2.3.5.

Satisfiability and Validity

2.3.5.1.

Satisfiable Formulas

2.3.5.2.

2.3.5.3.

Unsatisfiable Formulas

2.3.5.4.

Relationship Between Concepts

2.3.6.

Logical Consequence

2.3.6.1.

Definition of Entailment

2.3.6.2.

Semantic Consequence

2.3.6.3.

Testing for Entailment

2.3.6.4.

Use in Reasoning

2.4.

2.4.1.

Conjunctive Normal Form

2.4.1.1.

Definition and Structure

2.4.1.2.

Literals and Clauses

2.4.1.3.

Converting to CNF

2.4.1.4.

Importance in Automated Reasoning

2.4.2.

Disjunctive Normal Form

2.4.2.1.

Definition and Structure

2.4.2.2.

Converting to DNF

2.4.2.3.

2.4.3.

Conversion Algorithms

2.4.3.1.

Elimination of Implications and Biconditionals

2.4.3.2.

Moving Negations Inward

2.4.3.3.

Distribution Laws

2.4.3.4.

Simplification Techniques

2.4.4.

Other Normal Forms

2.4.4.1.

Negation Normal Form

2.4.4.2.

Full Disjunctive Normal Form

2.4.4.3.

Full Conjunctive Normal Form

Previous

1. Introduction to Logic in Computer Science

Go to top

Next

3. Proof Systems for Propositional Logic