Great Ideas in Theoretical Computer Science: Deductive Systems

Explore the foundations of theoretical computer science in this Spring 2015 lecture on Deductive Systems from CMU's 15-251 course. Delve into Hilbert's 10th problem, examine parentheses and binary tree examples, and investigate the ATM and Parenthesis deductive systems. Refresh your understanding of Propositional Logic, including formal formula definitions, truth assignments, and logical equivalences. Learn to analyze satisfiability and tautologies through practical examples, enhancing your grasp of fundamental computer science concepts.

Syllabus

Intro
Hilbert's 10th problem
An example involving parentheses
Example binary tree deduction
Binary tree terminology
The ATM deductive system
Parenthesis deductive system
One final question
Propositional Logic Refresher
Formally defining formulas
Truth assignment V: setting of Tor F for each variable.
In the binary tree perspective
Satisfiability
All well-formed formulas
Logical Equivalence
Example equivalences
Problem: Show (((x+y)^x) +y) is a tautology.