[FrontPage] [TitleIndex] [WordIndex]

In progress

• Scribe - Rob Quimby
• Editor - Matt Colyer
• Editor -

# Notes from Tuesday, October 19

## Logic

Logic is fundamentally an attempt to describe how thought works. A classic example is:

```All men are mortals
Socrates is a man
====================
Socrates is a mortal```

The logic we're most concerned with is Propositional Logic (Boolean Algebra). The main distinguishing feature of propositional logic is that everything is either true or false, there are no states inbetween.

## Notation

• True: T, 1, #t
• False: F, ┴, 0, #f

• Conjunction: ^, &, ab, and

• Disjunction: |, +, ˇ, or

• Negation: ¬, ~, overbar (ā), !, not

• Implication: ->,=>, the like

• Equivalence: =, <=>, <->, ≡

## Rules

• If ¬¬p, then p (Double Negation Elimination)
• If p^q, then p (Rule of Inference)
• If p implies q, and p, then q (modus ponens!)
• p^q implies p is a tautology (statement that is always true)
• (¬p)ˇ(p) Another tautology (the law of excluded middles)

• pˇq = ¬((¬p)^(¬q)) De Morgan's Law

• p^q = ¬((¬p)ˇ(¬q)) Also De Morgan's Law

Soundness means that true premises always lead to true conclusions.

Completeness means that anything that is true can be derived or proved.

## Forms

There are two main forms commonly used to express boolean algebra statements: Conjunctive and disjunctive.

1. Conjunctive form statements are composed of conjunctions of disjunctions
• (PˇQ) ^ (¬Pˇ¬Q) is a conjunctive XOr.

• Verifying truth for this form is generally O(n), but finding it can be (2^n)
2. Disjunctive form statements are composed of disjunctions or conjunctions.
• (¬PQ) &#711; (P¬Q) is a disjunctive XOr.

• Both finding and verifying these statements tends to be O(n).

## Truth Tables

A truth value is a value of T or F for a proposition. These often end up in truth tables, like the one below.

 p q p^q 0 0 0 0 1 0 1 0 0 1 1 1

2013-07-17 10:43
The text passage is a set of notes on logic and propositional logic, including definitions, rules, and forms. It does not contain any mathematical questions or answers to such questions.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
[FrontPage] [TitleIndex] [WordIndex]

In progress

• Scribe - Rob Quimby
• Editor - Matt Colyer
• Editor -

# Notes from Tuesday, October 19

## Logic

Logic is fundamentally an attempt to describe how thought works. A classic example is:

```All men are mortals
Socrates is a man
====================
Socrates is a mortal```

The logic we're most concerned with is Propositional Logic (Boolean Algebra). The main distinguishing feature of propositional logic is that everything is either true or false, there are no states inbetween.

## Notation

• True: T, 1, #t
• False: F, ┴, 0, #f

• Conjunction: ^, &, ab, and

• Disjunction: |, +, ˇ, or

• Negation: ¬, ~, overbar (ā), !, not

• Implication: ->,=>, the like

• Equivalence: =, <=>, <->, ≡

## Rules

• If ¬¬p, then p (Double Negation Elimination)
• If p^q, then p (Rule of Inference)
• If p implies q, and p, then q (modus ponens!)
• p^q implies p is a tautology (statement that is always true)
• (¬p)ˇ(p) Another tautology (the law of excluded middles)

• pˇq = ¬((¬p)^(¬q)) De Morgan's Law

• p^q = ¬((¬p)ˇ(¬q)) Also De Morgan's Law

Soundness means that true premises always lead to true conclusions.

Completeness means that anything that is true can be derived or proved.

## Forms

There are two main forms commonly used to express boolean algebra statements: Conjunctive and disjunctive.

1. Conjunctive form statements are composed of conjunctions of disjunctions
• (PˇQ) ^ (¬Pˇ¬Q) is a conjunctive XOr.

• Verifying truth for this form is generally O(n), but finding it can be (2^n)
2. Disjunctive form statements are composed of disjunctions or conjunctions.
• (¬PQ) &#711; (P¬Q) is a disjunctive XOr.

• Both finding and verifying these statements tends to be O(n).

## Truth Tables

A truth value is a value of T or F for a proposition. These often end up in truth tables, like the one below.

 p q p^q 0 0 0 0 1 0 1 0 0 1 1 1

2013-07-17 10:43
user
The text passage is a set of notes on logic and propositional logic, including definitions, rules, and forms. It does not contain any mathematical questions or answers to such questions.

TYPE: NO_QUESTION