Sound and complete, Computer Engineering

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)

Posted Date: 3/21/2013 1:55:44 AM | Location : United States







Related Discussions:- Sound and complete, Assignment Help, Ask Question on Sound and complete, Get Answer, Expert's Help, Sound and complete Discussions

Write discussion on Sound and complete
Your posts are moderated
Related Questions
What are the issues of software development One of main issues in software development today is quality. Software must be properly documented and implemented. The notion of sof

Loop Level This is one more level of parallelism where iterative loop instructions can be parallelized. Fine Granularity  size is used at this level also. Simple loops in a

Give example of Real time (transaction) processing Using this illustration of booking seats on a flight, below sequence of events would occur: -  Customer/travel agent conta

Q. Advantages and Disadvantage of Message Passage Programming? Advantages of Message Passage Programming     Portable It is less error prone Offers excellent

Distinguish between ROM, PROM, EPROM, EEPROM. Ans: ROM: It also called Read Only Memory is a Permanent Memory. The data is permanently stored and cannot be changed in Perm

What are the Input devices Various devices are available for data input on graphics workstations. Most systems have a keyboard and one or more additional devices specially desi

Web pages or materials which are in the form of hypermedia documents accessed through Internet can be located anywhere in world. No matter from where they originated, most Web d

What is the purpose of zero (z) flag and carry (c) flag? Carry flag holds the carry after addition or the borrow after subtraction. Carry flag also indicates error conditions,

How to Calculate the Logic Circuit Outputs? Once the Boolean expression for a circuit output has been acquired, the output logic level can be determined for any set of input le

Q. How the Characters used in operand data type? A common form of data is character or text strings. Characters are signified in numeric form mostly in ASCII (American Standard