Fdtxjr

Why are PDP-7-style microprogrammed instructions out of vogue?

Store Dynamic-accessible hidden metadata in a cell

Are spiders unable to hurt humans, especially very small spiders?

Is every episode of "Where are my Pants?" identical?

Would an alien lifeform be able to achieve space travel if lacking in vision?

What is the padding with red substance inside of steak packaging?

Single author papers against my advisor's will?

Word for: a synonym with a positive connotation?

US Healthcare consultation for visitors

Simulating Exploding Dice

Match Roman Numerals

How did the audience guess the pentatonic scale in Bobby McFerrin's presentation?

What to do when moving next to a bird sanctuary with a loosely-domesticated cat?

Can the Right Ascension and Argument of Perigee of a spacecraft's orbit keep varying by themselves with time?

One-dimensional Japanese puzzle

Can withdrawing asylum be illegal?

What was the last x86 CPU that did not have the x87 floating-point unit built in?

How do spell lists change if the party levels up without taking a long rest?

Using dividends to reduce short term capital gains?

Can each chord in a progression create its own key?

My body leaves; my core can stay

Could an empire control the whole planet with today's comunication methods?

60's-70's movie: home appliances revolting against the owners

Sub-subscripts in strings cause different spacings than subscripts

Relation between height and length of a formula in First-Order Logic

-1

1

$begingroup$

Definition: The height $mathrmht(p)$ of a formula $p$ is defined by

1. 
   $mathrmht(p) = 1$, for an atom formula $p$


2. 
   $mathrmht(a)+1 = mathrmht((neg a))$, for binary formula $a$
   

Definition. The size or length $|A|$ of a formula $A$ is the number of occurrences of logical symbols and atomic formulas in $A$.

Prove that for any binary formula $p$, $|p|geq mathrmht(p)$.

I tried induction on the length with base case that
if $|p| = 1$ so its an atomic formula and by definition $mathrmht(p) = 1$. From that point I am stuck.

logic first-order-logic predicate-logic

share|cite|improve this question

edited Mar 24 at 19:16

DANIEL SHALAM

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For atomic $p : |p|=1 ge text ht(p)=1$.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:15
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For $A := lnot B$ we have to assume that $| B| ge text ht(B)$.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thus, $| A |= | lnot B |= |B|+1 ge text ht(B)+1= text ht(A)$.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Finally, you have to consider the case for $A := B circ C$ where $circ$ is a binary connective.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:51
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Somone edited my qustion incorrectly can you answer it now ? thanks.
  $endgroup$
  – DANIEL SHALAM
  Mar 24 at 19:18
  
  

  
  
  
  

 | 
show 3 more comments

-1

1

$begingroup$

Definition: The height $mathrmht(p)$ of a formula $p$ is defined by

1. 
   $mathrmht(p) = 1$, for an atom formula $p$


2. 
   $mathrmht(a)+1 = mathrmht((neg a))$, for binary formula $a$
   

Definition. The size or length $|A|$ of a formula $A$ is the number of occurrences of logical symbols and atomic formulas in $A$.

Prove that for any binary formula $p$, $|p|geq mathrmht(p)$.

I tried induction on the length with base case that
if $|p| = 1$ so its an atomic formula and by definition $mathrmht(p) = 1$. From that point I am stuck.

logic first-order-logic predicate-logic

share|cite|improve this question

edited Mar 24 at 19:16

DANIEL SHALAM

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For atomic $p : |p|=1 ge text ht(p)=1$.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:15
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  For $A := lnot B$ we have to assume that $| B| ge text ht(B)$.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:16
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thus, $| A |= | lnot B |= |B|+1 ge text ht(B)+1= text ht(A)$.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:42
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Finally, you have to consider the case for $A := B circ C$ where $circ$ is a binary connective.
  $endgroup$
  – Mauro ALLEGRANZA
  Mar 24 at 17:51
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Somone edited my qustion incorrectly can you answer it now ? thanks.
  $endgroup$
  – DANIEL SHALAM
  Mar 24 at 19:18
  
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

Definition: The height $mathrmht(p)$ of a formula $p$ is defined by

1. 
   $mathrmht(p) = 1$, for an atom formula $p$


2. 
   $mathrmht(a)+1 = mathrmht((neg a))$, for binary formula $a$
   

Definition. The size or length $|A|$ of a formula $A$ is the number of occurrences of logical symbols and atomic formulas in $A$.

Prove that for any binary formula $p$, $|p|geq mathrmht(p)$.

I tried induction on the length with base case that
if $|p| = 1$ so its an atomic formula and by definition $mathrmht(p) = 1$. From that point I am stuck.

logic first-order-logic predicate-logic

share|cite|improve this question

edited Mar 24 at 19:16

DANIEL SHALAM

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95

$endgroup$

share|cite|improve this question

edited Mar 24 at 19:16

DANIEL SHALAM

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95

share|cite|improve this question

edited Mar 24 at 19:16

DANIEL SHALAM

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95

asked Mar 24 at 16:57

DANIEL SHALAMDANIEL SHALAM

95