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

Bootstrap, The device is packaged in a 80 pin PLCC device as shown.The main...

The device is packaged in a 80 pin PLCC device as shown.The main groupings of the pins are as follows Port A PA0 - PA7 Parallel Port or Timer Port B PB0 - PB7 Parallel Port or High

Determine about the blocking suspicious behaviour, Determine about the bloc...

Determine about the blocking suspicious behaviour The response could be spontaneous and automatic, with an option to generate the alert message manually. The history recorded i

Object oriented systems analysis and design, Analysis and design form the b...

Analysis and design form the basis on any significant software artifact. Analysis is critical in terms of making sure that the final artifact actually meets user requirements (ie b

Slope deflection equations, Slope Deflection Equations for a Member: I...

Slope Deflection Equations for a Member: In this section, we will develop a few general equations needed for further discussion in the moment distribution context. Fig

Disadvantages of asynchronous and synchronous reset, What are disadvantages...

What are disadvantages of the asynchronous reset and synchronous reset? Disadvantages of asynchronous reset: Make sure that the release of the reset can arise within one c

Bernstein conditions for detection of parallelism, Bernstein Conditions for...

Bernstein Conditions for Detection of Parallelism For implementation of instructions or block of instructions in parallel, it should be guaranteed that the instructions are ind

Illustrate the basic structure of the von neumann machine, Illustrate the b...

Illustrate the basic structure of the von Neumann machine The following figure shows basic structure of the von Neumann machine. A von Neumann machine has only a single path be

Data rate limitations in PSTN's by using nyquist theorem, Explain with the ...

Explain with the help of Nyquist theorem, the data rate limitations in PSTN's. Data rates in PSTNs : A voice channel in a public switched telephone network is band restricted

What is arrays pointers, Q. What is Arrays Pointers? An array is a coll...

Q. What is Arrays Pointers? An array is a collection of similar type of data. Arrays are extremely popular data structures in parallel programming because of their easiness of

What are kinds of models, What are kinds of models? Class model - Objec...

What are kinds of models? Class model - Objects in the system and their relationships. State model - Life history of the objects. Interaction model - Interactions between

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