Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Propositional Calculus

Description

This lecture covers the fundamentals of formal logic and theoretical computer science, including the basics of propositional calculus, effective procedures, and complexity theory. Topics include predicate calculus, set theory, proofs, NP-completeness, and the importance of studying propositional calculus.

Official source

Related concepts (32)

Logic

Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or logical truths. It studies how conclusions follow from premises due to the structure of arguments alone, independent of their topic and content. Informal logic is associated with informal fallacies, critical thinking, and argumentation theory. It examines arguments expressed in natural language while formal logic uses formal language.

Formal system

A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A formal system is essentially an "axiomatic system". In 1921, David Hilbert proposed to use such a system as the foundation for the knowledge in mathematics. A formal system may represent a well-defined system of abstract thought.

Propositional calculus

Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations between propositions, including the construction of arguments based on them. Compound propositions are formed by connecting propositions by logical connectives. Propositions that contain no logical connectives are called atomic propositions.

Formal proof

In logic and mathematics, a formal proof or derivation is a finite sequence of sentences (called well-formed formulas in the case of a formal language), each of which is an axiom, an assumption, or follows from the preceding sentences in the sequence by a rule of inference. It differs from a natural language argument in that it is rigorous, unambiguous and mechanically verifiable. If the set of assumptions is empty, then the last sentence in a formal proof is called a theorem of the formal system.

Mathematical logic

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

Related lectures (53)

Concept of Proof in Mathematics

Delves into the concept of proof in mathematics, emphasizing the importance of evidence and logical reasoning.

Recursive Enumerability: Turing Machines and Undecidable Languages

Covers recursively enumerable languages, Turing machines, and the construction of undecidable languages.

Introduction & Propositional Logic

Covers the basics of propositional logic, logical connectives, truth tables, and compound propositions.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Coq: Introduction