[<< wikibooks] Logic for Computer Scientists/Predicate Logic/Predicate Logic
== Predicate Logic ==
When we introduced propositional logic we argued in treating the
electrical circuit example (circuit), that a string like

  
    
      
        h
        i
        g
        h
        (
        i
        n
        v
        1
        ,
        o
        )
      
    
    {\displaystyle high(inv1,o)}
   can be read intuitively as "the output of inverter
1 is high", but then we abstracted from this internal structure of
the proposition  and further on we represented the proposition by a
simple string like  "the_output_of_inverter_1_ is_high". In
the formal parts of the calculus we even assumed more abstract just a
given countable set of propositions 
  
    
      
        {
        
          P
          
            1
          
        
        ,
        ⋯
        ,
        
          P
          
            i
          
        
        ,
        ⋯
        }
      
    
    {\displaystyle \{P_{1},\cdots ,P_{i},\cdots \}}
   . Until
now, we investigated a logical language that was able to deal with
connecting these propositions,
In this section we will have a closer look into the structure of
propositions. We will be able to explicitly refer to objects like
the inverter 
  
    
      
        i
        n
        v
        1
      
    
    {\displaystyle inv1}
   or its output 
  
    
      
        o
      
    
    {\displaystyle o}
   in the sentences of our
language,. Besides this domain, we will introduce the new concept
of a variable, which stands for an arbitrary object of our domain.
Hence, we will be able to write e.g. 
  
    
      
        h
        i
        g
        h
        (
        x
        ,
        o
        )
      
    
    {\displaystyle high(x,o)}
   to denote the fact
that the output of a 
  
    
      
        x
      
    
    {\displaystyle x}
   is high.  As a consequence of this concept
we will have quantifiers, which allow for sentences like 
  
    
      
        ∃
        x
        
        h
        i
        g
        h
        (
        x
        ,
        o
        )
      
    
    {\displaystyle \exists x\;high(x,o)}
  , with an intended meaning that there exists an
object 
  
    
      
        x
      
    
    {\displaystyle x}
  , whose output 
  
    
      
        o
      
    
    {\displaystyle o}
   is high, or 
  
    
      
        ∀
        x
        
        h
        i
        g
        h
        (
        x
        ,
        o
        )
      
    
    {\displaystyle \forall x\;high(x,o)}
  
with an intended meaning that for all objects 
  
    
      
        x
      
    
    {\displaystyle x}
   output 
  
    
      
        o
      
    
    {\displaystyle o}
   is
high,
Together with these new concepts it will be possible to express rather
abstract properties of elements from the domain. Assume, e.g. that we
want to introduce the concept of elements in a circuit to be
connected. We could say 
  
    
      
        c
        o
        n
        n
        e
        c
        t
        e
        d
        (
        i
        n
        v
        1
        ,
        i
        n
        v
        2
        )
      
    
    {\displaystyle connected(inv1,inv2)}
   and

  
    
      
        c
        o
        n
        n
        e
        c
        t
        e
        d
        (
        i
        n
        v
        2
        ,
        i
        n
        v
        3
        )
      
    
    {\displaystyle connected(inv2,inv3)}
  . Now, with the intended meaning of being
connected, we can assume, that 
  
    
      
        i
        n
        v
        1
      
    
    {\displaystyle inv1}
   and 
  
    
      
        i
        n
        v
        3
      
    
    {\displaystyle inv3}
   are connected as
well. Of course, we could introduce the new sentence 
  
    
      
        c
        o
        n
        n
        e
        c
        t
        e
        d
        (
        i
        n
        v
        1
        ,
        i
        n
        v
        3
        )
      
    
    {\displaystyle connected(inv1,inv3)}
   to express this; but the disadvantage is obvious: this have to
be done for all objects from our domain. In predicate logic this
property of transitivity of connectedness can be expressed without
referring to explicit objects by the following sentence:

  
    
      
        ∀
        x
        ∀
        y
        ∀
        z
        (
        (
        c
        o
        n
        n
        e
        c
        t
        e
        d
        (
        x
        ,
        y
        )
        ∧
        c
        o
        n
        n
        e
        c
        t
        e
        d
        (
        y
        ,
        z
        )
        )
        →
        c
        o
        n
        n
        e
        c
        t
        e
        d
        (
        x
        ,
        z
        )
        )
      
    
    {\displaystyle \forall x\forall y\forall z((connected(x,y)\land connected(y,z))\to connected(x,z))}