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

Determine the binary equivalent of hexadecimal FA, The binary equivalent of...

The binary equivalent of (FA) 16   is ? Ans. (FA) 16 = (11111010) 10

Retina - biometric computer security systems, Retina - Biometric Computer S...

Retina - Biometric Computer Security Systems The next security technology that explained in this report is retina security technology which is very famous in a lot of spy movi

Instruction-execution cycle, Problem (a) Using a labelled diagram of ...

Problem (a) Using a labelled diagram of an Instruction-Execution cycle, describe how a CPU executes single machine instructions by referring to the five main operations.

What is pipelining, What is pipelining? The overlapping of implementati...

What is pipelining? The overlapping of implementation of successive instructions is known as pipelining.

Minimum total number of shelv, Write a program that finds the minimum total...

Write a program that finds the minimum total number of shelv, C/C++ Programming

Find out the correction to be applied in decimal adder, The correction to b...

The correction to be applied in decimal adder to the generated sum is ? Ans. 00110 is the generated sum when the correction to be applied in decimal adder. While the 4 bit su

Operation research, how to implement a modified distribution method using c...

how to implement a modified distribution method using c/c++

Where virtual memory is used, Where Virtual memory is used ? Ans. Virtu...

Where Virtual memory is used ? Ans. Virtual memory is utilized in all main commercial operating systems.

Pruning - artificial intelligence, Pruning - Artificial intelligence Re...

Pruning - Artificial intelligence Remember that pruning a search space means deciding that particular branches should not be explored. If an agent  surly  knows that exploring

Demorgan''s first theorem, DeMorgan's first theorem shows the equivalence o...

DeMorgan's first theorem shows the equivalence of which logic gate ? Ans. DeMorgan's first theorem depicts the equivalence of NOR gate and Bubbled AND gate. For De Morgan's

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