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

What layers are covered under end to end layer connectivity, What layers ar...

What layers are covered under end to end layer connectivity? The layers 4 to 7 of ISO-OSI reference model communicate along with peer entities into the end systems. There is n

Enumerate about the decimal arithmetic unit, Enumerate about the Decimal Ar...

Enumerate about the Decimal Arithmetic Unit The user of the computer input data in decimal numbers and receives output in the decimal form. But a CPU with ALU can perform arith

What is the linkage section used for, The linkage section is used to pass d...

The linkage section is used to pass data from one program to one more program or to pass data from a PROC to a program.

What is cartridge drive, Q. What is Cartridge Drive? Cartridge Drive: ...

Q. What is Cartridge Drive? Cartridge Drive: A cartridge is a protective covering or case which is used to hold a magnetic tape, disk, a printer ribbon or toner. Contents are

What are the measures to be taken in the design, What are the measures or p...

What are the measures or precautions to be taken in the Design when the chip has both analog and digital portions? As today's IC has analog components also inbuilt, some design

Operating system., what is the minimum number of page faults for an optimal...

what is the minimum number of page faults for an optimal page replacement strategy?

What are null values, What are null values? If the value of a field in ...

What are null values? If the value of a field in a table is indeterminate or unknown, it is known as a null value.

Transportation model, advantages and disadvantages of northwest corner meth...

advantages and disadvantages of northwest corner method and least cost method

Show the process management for parallel virtual machine, Q. Show the Proce...

Q. Show the Process Management for parallel virtual machine? Process Management  int pvm_mytid( void ) Returns the tid of the calling process. Tid values les

Sigmoid units-artificial intelligence, Sigmoid units - Artificial intellige...

Sigmoid units - Artificial intelligence Remember that the function inside units take as input the weighted sum, S, of the values coming from the units associated to it. The fun

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