Sound and complete, Computer Engineering

Assignment Help:

Dictator Dim wants to replace counting, in particular, counting the population of his land. To keep an accurate population count, Dictator Dim has instructed his secretary to add one + symbol to a record each time a citizen is born, and one - symbol to the record whenever a citizen dies. This has been going on ever since his rule began.

Dictator Dim is not concerned so much with the actual total population of his lands, just with the net change in population since his rule began. He would be forever disgraced if the net population change were ever negative. Refusing to solve this problem by counting, Dictator Dim instructs his secretary to find a sound and complete logic for the subset of all records that would not disgrace him.
More formally, define the following truth concept WFF's = {+; -}, i.e., all strings composed of only plus and minus symbols.
A WFF x is true if every prefix of x contains at least as many + symbols as - symbols.

Find a logic for this truth concept by proving that it is sound and complete. Hint: it may help to define additional judgement form(s)


Related Discussions:- Sound and complete

Discuss in detail the subscriber loop systems, Discuss in detail the subscr...

Discuss in detail the subscriber loop systems. Subscriber Loop System: Every subscriber in a telephone network is linked usually to the nearest switching office by means of w

Use of hypertext links in internet access, Use of Hypertext links in Intern...

Use of Hypertext links in Internet access From the user's point of view, the Web having of a vast, worldwide collection of documents i.e. pages. Every page may have links (poin

Calculate traffic lost in a particular exchange, In a particular exchange d...

In a particular exchange during busy hour 1200 calls were offered to a group of trunks, during this time 6 calls were lost. The average call duration being 3 minutes Calculate Tr

Why stored program control gains superiority over hard wired, In what way i...

In what way is stored program control superior to hard wired control? The SPC gains superiority over hard wired because of following points: SP C Ha

Illustrate high performance fortran, In 1993 High Performance FORTRAN Forum...

In 1993 High Performance FORTRAN Forum which is a group of academicians and many leading software and hardware vendors in field of parallel processing established an informal langu

What is a multitape tm, What is a multitape TM?  A  multi-tape  Turing ...

What is a multitape TM?  A  multi-tape  Turing  machine  having  of  a  finite  control  with  k-tape  heads  and k-tapes each tape is infinite in both directions. On a one mov

Mpi, write an8086 alp to exchange a block of N bytes of data between sourc...

write an8086 alp to exchange a block of N bytes of data between source and destination

Properties of e-cash, Properties: 1.  Monetary Value: Monetary value mu...

Properties: 1.  Monetary Value: Monetary value must be backed by either cash, bank - authorized credit cards or bank certified cashier's cheque. 2.  Interoperability: E-cash

Explain the process of inter-register signalling, Explain the process of in...

Explain the process of inter-register signalling. Registers are utilized in common control exchanges to store and analyze routing data. They are given on a common basis is a

Associative memory organisations, Associative Memory Organisations The ...

Associative Memory Organisations The associative memory is organised in w words with b bits per word. In w x b array, every bit is known a cell. Each cell is made up of a flip-

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd