Introduction to Logic, Logic Programming Concepts and Languages (Part 1)

Posted on | Post modified | In , , , ,

Mathematical Formalizations in Logic

Why formalize language?

  • to remove ambiguity

  • to represent facts on a computer and use it for proving, proof-checking, etc.

  • to detect unsound reasoning in arguments

    What is unsound?

Logic

  • Mathematical logic is a tool for dealing with formal reasoning.
    • formalization of natural language and reasoning methods
  • Logic does:
    • assess if an argument is Valid or Invalid
  • Logic does not directly:
    • assess the truth of atomic statements

Propositional Logic or the Logic of Compound Statements

This is the study of:

  • the structure (syntax) and
  • the meaning (semantics) of (simple and complex) propositions

The key questions are:

  • how is the truth value of a complex proposition obtained from the truth value of its simpler components?
  • which propositions represent correct reasoning arguments?

What is a Proposition

A proposition is a sentence that is either true or false, but not both

  • Examples of simple propositions:
    • John is a student
    • 5 + 1 = 6
    • 426 > 1721
    • It is 92 degrees outside right now.
  • Eaxmple of a complex proposition:
    • Tom is five and Mary is six.
  • Sentences which are not propositions:
    • Did Steve get an A on the exam? (this is a query)
    • Go away! (this is an order)

Proposition Forms or Formulas

In studying properties of propositions we represent them by expressions called proposition forms or formulas built from the followings:

  • propositional variables (atoms), which represent simple propositions
  • connective symbols, which representing logical connectives

Connectives

Formulas

Determining Truth of a Formula

  • Atomic formulae: given

  • Compound formulae: via meaning of the connectives

    • The semantics of logical connectives determines how propositional formulas are evaluated depending on the truth values assigned to propositional variables
    • Each possible truth assignment or valuation for the propositional variables of a formula yields a truth value. The different possibilities can be summarized in a truth table.

Evaluation of Formulas - Truth Tables

A truth table for a formula lists all possible situations of truth or falsity, depending on the values assigned to the propositional variables of the formula.

How to construct truth tables?

  • There are two choices (true or false) for each of n variables, so in general there are 2**n rows for n variables.
  • A systematic procedure (an algorithm) is necessary to make sure you construct all rows without duplicates.
    • construct the rows systematically:
      • count in binary: 000, 001, 010, 011, 100, …
      • the rightmost column must be computed as a function of all the truth values in the row

Language: Syntax of Formulas

  • The formal language of propositional logic can be specified by grammar rules

  • The syntactic structure of a complex logical expression must be unambiguous

    ::=

    ​ | (~)

    ​ | ( and )

    ​ | ( or )

    ​ …

    ::= p | q | r | …

  • Simplified Syntax

    • In arithmetic one often species a precedence among operators (say, times ahead of plus) to eliminate the need for some parentheses in certain programming languages.

    • The same can be done for the logical connectives, though deleting parentheses may cause confusion.

    • Precedence and associative

      • Avoid confusion - use parentheses

Vocabularies

Reference

Lecture Slide: Introduction to Logic, Logic Programming Concepts and Languages