CSCE 222 Lecture 4

« previous | Wednesday, January 26, 2011 | next »

Propositional Logic

(See CSCE 222 Chapter 1.1→)

Proposition: a statement that is either true or false

EX: Jack is taller than Jill

Prop. Logic describes ways to combine true statements with help of #Connectives to produce other true statements

Connectives

Connective	Symbol
negation	¬
and	∧
or	∨
exclusive or	⊕
conditional	→
biconditional	↔

Semantics

a	b	¬ a	a ∧ b	a ∨ b	a ⊕ b	a → b	a ↔ b
F	F	T	F	F	F	T	T
F	T	T	F	T	T	T	F
T	F	F	F	T	T	F	F
T	T	F	T	T	F	T	T

Backus Naur Form Derivation rules

Similar to Grammars

<symbol>	::=	<symbol1> <symbol2> … <symboln>
single symbol non-terminal		symbol that resides only on right hand side terminal

Example: Single digit binary number

can be specified in Backus Naur Form (BNF) by:

• <binary digit> ::= 0
• <binary digit> ::= 1

Abbreviation:

• <binary digit> ::= 0 | 1

Example: Multi-digit binary number

<binary number>	::=	<binary number> <binary digit> | <binary digit>
<binary digit>	::=	0 | 1

Language of Propositional Logic

((a → b) ↔ (¬a ∨ b))

defined by following grammar:

<formula>	::=	¬ <formula>
	|	(<formula> ∧ <formula>)
	|	(<formula> ∨ <formula>)
	|	(<formula> ⊕ <formula>)
	|	(<formula> → <formula>)
	|	(<formula> ↔ <formula>)
	|	<symbol>
<symbol>	::=	{a, a0, a1, a2, a3, … zn}

Example

((a ∧ b) ∨ ¬ c)

1. (<formula> ∨ <formula>)
2. ((<formula> ∧ <formula>) ∨ ¬ <formula>)
3. ((<symbol> ∧ <symbol>) ∨ ¬ <symbol>)

Formation Tree

$((a\wedge b)\vee \neg c)$
$(a\wedge b)$		$\neg c$
$a$	$b$	$c$

valuations

interpretations

assigning values to symbols

degree

number of connectives in a statement

tautology

Continued Intro to Ruby

Download from http://www.ruby-lang.org/en/ (included by default on many Linux and Mac OS X systems

• Very popular open source interpreted programming language
• Fully object-oriented, but includes concepts from functional programming languages
• dynamically typed (no declarations), flexible, and very expressive.

Interactive ruby interpreter irb

Objects and Classes

(Almost) everything is a class/object in Ruby. Find out which object a class belongs to by typing obj.class

To list available object methods, type obj.methods.sort

Built-in data types

• Integer (1, 2, -1, 10**1000)
• Float (1.2, -3.14)
• Array (a = [1,2,3])
• Range (1..1000)
• String "abc"
  • Interpolation "Evaluate in-string: #{1+2} == 3" (not with single quotes)
• Symbol or immutable String (:name)
• Hash {:name => "George", :age => 12}

Variables

var	lower case variables are local variables
@var	instance variables (same scope as self)
$var	global variables

class Person
  attr_accessor :name, :age
  def full_info
    return "#{@name} is #{@age} years old"
  end
end

# Usage:
p = Person.new
p.name = 'George'
p.age = 12

puts p.full_info # "George is 12 years old"

Enumerable Module

Ruby has for loops and similar constructs, but these methods are more common:

[1,2,3].each { |number| puts 2*number } # print out twice each number for all numbers
[1,2,3].any? { |number| number.even? } # are there any even numbers?
[2,4,6].all? { |number| number.even? } # are ALL even numbers? 
[1,2,3].map { |number| number**2 } # returns a created array by squaring each item
[1,2,3].inject(:+) # calculate sum of array (operators can be overloaded)
[1,2,3].inject(:*) # calculate product of array

Extending Existing Classes

class Integer
  def factorial # there is no factorial method defined for vector
    (1..self).inject(:*)
  end
end